4073 - Gardens of Incadelia

Created by Humberto Díaz Suárez
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 22000 MS | Test Time: 2000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

The Republic of Incadelia is known for its many natural wonders. Among them is one of the world's largest botanical gardens. It's divided into numerous smaller walled gardens, with tunnels allowing movement between pairs of them. The tunnels have been painted and decorated to create elaborate works of art worthy of their own visit. When Jai traveled to Incadelia to celebrate her graduation, she knew exactly where she needed to go.

Jai wants to see a lot of gardens, but she insists on touring them in a certain way. She chooses a pair of interesting gardens, then tries to devise a route from one of them to the other and back, ending up where she began. To ensure that she gets the most out of the experience, Jai wants to plan her route so that she avoids passing through any tunnel more than once (in either direction).

Meeting that requirement can be difficult, or even impossible. Plus, there are so many tunnels that Incadelian engineers had to come up with a compact format to describe them on maps. Jai's last semester was tough and she could use a break from algorithms. Could you check for her whether it's possible to walk between some pairs of gardens?
La República de Incadelia es conocida por sus muchas maravillas naturales. Entre ellas está uno de los jardines botánicos más grandes del mundo. Está dividido en numerosos jardines amurallados pequeños, con túneles que permiten moverse entre pares de ellos. Los túneles están pintados y decorados para crear obras de arte elaboradas dignas de su propia visita. Cuando Jai viajó a Incadelia para celebrar su graduación, ella supo exactamente a donde debía ir.

Jai desea ver muchos jardines, pero insiste en visitarlos de una manera particular. Ella escoge un par de jardines interesantes y trata de idear una ruta desde uno hasta el otro y volviendo, tal que termina donde comenzó. Para asegurar que le saque provecho a la experiencia, Jai quiere planificar su ruta de tal forma que evite pasar por cualquier túnel más de una vez (en cualquier dirección).

Puede ser difícil cumplir con ese requisito, o hasta imposible. Además, hay tantos túneles que ingenieros incadelianos tuvieron que inventar un formato compacto para describirlos en mapas. El último semestre de Jai fue duro y le gustaría un descanso de los algoritmos. ¿Podrías revisar por ella si es posible caminar entre algunos pares de jardines?
The Republic of Incadelia is known for its many natural wonders. Among them is one of the world's largest botanical gardens. It's divided into numerous smaller walled gardens, with tunnels allowing movement between pairs of them. The tunnels have been painted and decorated to create elaborate works of art worthy of their own visit. When Jai traveled to Incadelia to celebrate her graduation, she knew exactly where she needed to go.

Jai wants to see a lot of gardens, but she insists on touring them in a certain way. She chooses a pair of interesting gardens, then tries to devise a route from one of them to the other and back, ending up where she began. To ensure that she gets the most out of the experience, Jai wants to plan her route so that she avoids passing through any tunnel more than once (in either direction).

Meeting that requirement can be difficult, or even impossible. Plus, there are so many tunnels that Incadelian engineers had to come up with a compact format to describe them on maps. Jai's last semester was tough and she could use a break from algorithms. Could you check for her whether it's possible to walk between some pairs of gardens?

Input specification

The input will consist of several test cases. Each case will begin with a line containing two integers N (2 ≤ N ≤ 5 × 104) and K (2 ≤ K ≤ 105), separated by a space, indicating the number of gardens and the number of tunnel descriptions, respectively. The following K lines will each contain a tunnel description. Each will consist of three integers A, B, and C (1 ≤ A ≤ N, 1 ≤ B ≤ C ≤ N), separated by spaces, indicating that garden A has separate tunnels that lead to each garden in the range [B, C].

After this, there will be a line containing an integer Q (1 ≤ Q ≤ 105), denoting the number of questions. The following Q lines will each contain a pair of distinct integers X and Y (1 ≤ X, Y ≤ N), separated by a space. These will represent a question: can Jai walk from garden X to garden Y and back as described above?

Every tunnel will appear in exactly two tunnel descriptions - once for each of its endpoints. No garden will have a tunnel connecting it to itself and there will be at most one tunnel between any two gardens. The total number of gardens, the total number of tunnel descriptions, and the total number of questions across all test cases will not exceed 105. The input will end with a line containing "0 0", which must not be processed as a test case.
La entrada consistirá de varios casos de prueba. Cada caso comenzará con una línea que contiene dos enteros N (2 ≤ N ≤ 5 × 104) y K (2 ≤ K ≤ 105), separados por un espacio, que indican el número de jardines y el número de descripciones de túneles, respectivamente. Cada una de las siguientes K líneas contendrá la descripción de un túnel. Cada descripción consistirá de tres enteros A, B, y C (1 ≤ A ≤ N, 1 ≤ B ≤ C ≤ N), separados por espacios, que indican que el jardín A tiene túneles independientes que lo conectan a cada jardín en el rango [B, C].

Después de esto habrá una línea que contiene un entero Q (1 ≤ Q ≤ 105), que denota el número de preguntas. Cada una de las siguientes Q líneas contendrá un par de enteros distintos X y Y (1 ≤ X, Y ≤ N), separados por un espacio. Estos representaran una pregunta: ¿Jai puede caminar desde el jardín X hasta el jardín Y y regresar como se describió arriba?

Cada túnel sera parte de exactamente dos descripciones de túneles - una vez por cada uno de sus extremos. Ningún jardín tendrá un túnel que lo conecta a sí mismo y habrá a lo más un túnel entre cualquier par de jardines. El número total de jardines, el número total de descripciones de túneles y el número total de preguntas sobre todos los casos de prueba no excederá 105. La entrada terminará con una línea que contiene "0 0", que no debe ser procesada como un caso.
The input will consist of several test cases. Each case will begin with a line containing two integers N (2 ≤ N ≤ 5 × 104) and K (2 ≤ K ≤ 105), separated by a space, indicating the number of gardens and the number of tunnel descriptions, respectively. The following K lines will each contain a tunnel description. Each will consist of three integers A, B, and C (1 ≤ A ≤ N, 1 ≤ B ≤ C ≤ N), separated by spaces, indicating that garden A has separate tunnels that lead to each garden in the range [B, C].

After this, there will be a line containing an integer Q (1 ≤ Q ≤ 105), denoting the number of questions. The following Q lines will each contain a pair of distinct integers X and Y (1 ≤ X, Y ≤ N), separated by a space. These will represent a question: can Jai walk from garden X to garden Y and back as described above?

Every tunnel will appear in exactly two tunnel descriptions - once for each of its endpoints. No garden will have a tunnel connecting it to itself and there will be at most one tunnel between any two gardens. The total number of gardens, the total number of tunnel descriptions, and the total number of questions across all test cases will not exceed 105. The input will end with a line containing "0 0", which must not be processed as a test case.

Output specification

The output will consist of several lines for each test case. First, a line containing the string "Case #T:", where T is the number of the test case (starting from 1). Then one line for each question, answering with "yes" or "no". The order of the answers must follow the order of the questions. Do not include a blank line between test cases.
La salida consistirá de varias líneas por cada caso. Primero, una línea que contiene la cadena "Case ;jsessionid=AD37EAA9365FB1F31725F299EA9EAFC6#T:", donde T es el número del caso de prueba (comenzando con 1). Después una línea para cada pregunta, respondiendo con "yes" o "no". El orden de las respuestas debe seguir el mismo orden de las preguntas. No incluyas una línea vacía entre los casos de prueba.
The input will consist of several test cases. Each case will begin with a line containing two integers N (2 ≤ N ≤ 5 × 104) and K (2 ≤ K ≤ 105), separated by a space, indicating the number of gardens and the number of tunnel descriptions, respectively. The following K lines will each contain a tunnel description. Each will consist of three integers A, B, and C (1 ≤ A ≤ N, 1 ≤ B ≤ C ≤ N), separated by spaces, indicating that garden A has separate tunnels that lead to each garden in the range [B, C].

After this, there will be a line containing an integer Q (1 ≤ Q ≤ 105), denoting the number of questions. The following Q lines will each contain a pair of distinct integers X and Y (1 ≤ X, Y ≤ N), separated by a space. These will represent a question: can Jai walk from garden X to garden Y and back as described above?

Every tunnel will appear in exactly two tunnel descriptions - once for each of its endpoints. No garden will have a tunnel connecting it to itself and there will be at most one tunnel between any two gardens. The total number of gardens, the total number of tunnel descriptions, and the total number of questions across all test cases will not exceed 105. The input will end with a line containing "0 0", which must not be processed as a test case.

Sample input

3 4
1 2 3
2 1 1
2 3 3
3 1 2
1
1 2
6 9
1 2 3
2 1 1
2 3 3
3 1 2
3 6 6
4 5 6
5 6 6
5 4 4
6 3 5
2
1 6
3 4
0 0

Sample output

Case #1:
yes
Case #2:
no
no

Hint(s)

In the first case, Jai can walk from garden 1 to garden 2, then return by passing through garden 3. The second case has two questions. The answer to both is no, because while Jai could reach her destination, she could not return to the garden where she started without walking back through the tunnel between gardens 3 and 6.
En el primer caso, Jai puede caminar desde el jardín 1 hasta el jardín 2, y después regresar a través del jardín 3. El segundo caso tiene dos preguntas. La respuesta a ambas es no, porque aunque Jai podría alcanzar su destino, ella no podría regresar al jardín donde comenzó sin volver a pasar por el túnel entre los jardines 3 y 6.
In the first case, Jai can walk from garden 1 to garden 2, then return by passing through garden 3. The second case has two questions. The answer to both is no, because while Jai could reach her destination, she could not return to the garden where she started without walking back through the tunnel between gardens 3 and 6.