Description

Ash is a fledging pokemon trainer currently working his way to get badges of all eight gyms.
Although Ash is quite good at pokemon battles (thanks to his electric Ace), he is terrible at solving puzzles.
Notably Ash is having a hard time solving gym conveyor belt puzzles.
These puzzles consist of single-directional conveyor belts and a number of rooms.
For each belt, one can only step on the belt from one room, where the belt will transport the person to another room. The person cannot go back using the same belt (hence single-directional).

You are to write a C/C++ program that could help Ash to find if there exists a way for Ash to go from one room to another.
Your program should take in room and conveyor belt information and reachability queries from one room to another.
For each reachability query, if there is a way to reach from some start room to another end room, your program should output T, else F.

Your program MAY use C++ standard library headers.

Input

A new line containing the number of rooms M, the number of conveyor belts N, and the number of reachability queries to be answered P.
Then followed by N lines of conveyor belt information, in the format of START_ROOM_ID END_ROOM_ID per line, implying there is a conveyor belt going from room START_ROOM_ID to room END_ROOM_ID.
Finally, followed by P lines of reachability queries, in the format of START_ROOM_ID END_ROOM_ID per line, which is asking if we can reach room END_ROOM_ID from room START_ROOM_ID.
 

Constraints

• 1 < M <= 370
• 0 <= N <= M * (M - 1)
• 1 <= P <= 100000
• For every query, START_ROOM_ID != END_ROOM_ID
• The rooms will have ID from 0 to M - 1

 

Output

The answer to the reachability queries, one per line.

Sample Input  Download

Sample Output  Download

Discuss