Viaje a la Fiesta
Hay n ciudades numeradas desde hasta en Bytelandia. La primera ciudad es la capital. Existen rutas de autobuses: para cada ciudad , hay un bus que va de esta ciudad a la ciudad (), exactamente en esa dirección.
Existen tipos de platos nacionales numerados desde hasta . Cada ciudad tiene un plato especial , así que este y sólo este plato se puede comprar allí. Cada plato es de uno de los tipos de a .
Hay amigos numerados de a . El amigo está actualmente en la ciudad . Los amigos quieren celebrar una fiesta, por lo que necesitan reunirse en una ciudad. Obviamente, siempre es posible, pero quieren reunirse tan pronto como sea posible. Viajar en autobús toma una unidad de tiempo.
Ellos quieren comprar algunos platos para la fiesta siguiendo algunos requisitos:
Cada amigo debe comprar una cantidad igual de platos.
No debe haber dos tipos iguales de platos en la fiesta.
Cada amigo puede comprar solo los tipos de platos que corresponden a las ciudades que visitó.
Necesitas responder consultas (query en inglés). Cada consulta tiene la siguiente forma.Para cada consulta, debe calcular el número máximo posible de platos en la fiesta.
Dado tres enteros , y , imprima la respuesta para cada consulta en una línea. Los valores , y los detalles de la consulta deben tomarse de la entrada estándar como se describe en la sección de formato de entrada.
Entrada
La primera línea de la entrada contiene tres enteros separados por espacio: , y . La segunda línea contiene enteros separados por espacio . La tercera línea contiene enteros separados por espacio: . La de las siguientes lineas contienen la descipcion de la consulta. Cada consulta tiene el siguiente formato: un entero y entonces enteros separados entre si por un espacio.
Restricciones
Salida
Imprima lineas. La i-esima linea debe contener un entero simple denotando la respuesta de la i-esima consulta.
Ejemplo # 1 de Entrada
5 3 4
1 2 2 1
2 3 1 3 1
2 3 4
3 5 2 2
4 3 4 2 5
2 2 2
Ejemplo # 1 de Salida
2
3
0
0
Explicación
En la primera consulta, hay dos amigos. El primero esta en la ciudad y el segundo en la ciudad . Ellos se reuniran en la ciudad . Asi que el primero puede comprar un plato del tipo en la ciudad y el segundo puede comprar un plato del tipo en la ciudad .
En la segunda consulta, hay tres amigos. El primero esta en la ciudad , el segundo en la ciudad y el tercero esta en la ciudad . Ellos se encontraran en la ciudad 1. Asi, el primero puede comprar un plato de tipo en la ciudad , el segundo puede comprar un plato de tipo en la ciudad y el tercero puede comprar un plato de tipo en la ciudad .
En la tercera consulta, hay cuatro amigos, pero no hay manera de comprar algunos platos ya que hay 3 tipos de platos y . En la ultima consulta, hay dos amigos en la misma ciudad, asi, que obviamente no hay manera de comprar algunos platos.
Ejemplo # 2 de Entrada
11 6 3
1 2 2 4 5 4 5 8 9 4
5 6 1 1 2 3 2 3 4 5 2
3 3 10 8
4 6 5 10 10
2 9 6
Ejemplo # 2 de Salida
6
4
2
Comments