Swiss Olympiad in Informatics

Mouse Stofl visits some friends living in a huge subterrestrial mouse city called Underground City.
There are many mice living in this city. The city is organized such that each mouse family has its own private subsurface mousehole. These mouseholes are interconnected by tunnels, which can be used in both directions.
Unfortunatly not every mousehole is reachable from any other mousehole just using these tunnels. Since Mouse Stofl has a lot of friends and often travels between them, he wants to know which friends are reachable from which other friends, in order to optimize the order he visits them. Therefore he asks you questions of the form: is A reachable from B using the underground tunnels? Your task is to answer each of these questions.

After knowing all the tunnels which connect the mouseholes, you have to check for each query of the form given above whether there exists a connection between the two involved mouseholes.

The first line of the input contains three integers L, M and N (1 ≤ L ≤ 10'000, 1 ≤ M,N ≤ 200'000), the number of homes in Underground City (numbered from 1 to L), the number of tunnels connecting these homes and the number of queries.
Next, there are M lines describing the underground tunnels in the format «s_j e_j» (1 ≤ s_j, e_j ≤ L), where s_j denotes the mousehole (by its index) where tunnel j starts and e_j denotes the mousehole (by its index) where tunnel j ends.
On the following N lines, there are two integers a_k and b_k. This means that Stofl would like to know whether there exists an underground path from the mousehole with the index a_k to the mousehole with the index b_k.

Print for each of the N requests a single letter, the letter 'Y' if it is possible to reach mousehole b_k coming from mousehole a_k by using the underground tunnels of the city and 'N' otherwise (without quotes). The letters should be on one line and separated by a single space.

6 7 5
1 2
2 3
1 2
1 6
1 3
5 4
3 2
1 2
3 4
2 5
2 3
2 6

Y N N Y Y

7 5 1
1 3
2 3
5 2
4 5
4 6
1 6

Y

• Added second sample input/output for clarification
• To reach mousehole A from mousehole B, it does not matter how many tunnels Stofl has to use. Even if he has to visit all the other mouseholes first, they are still considered connected. See the second sample input for this case.

Submission form