| Submit | All submissions | Best solutions | Back to list |
EIHCON - Is there a path? |
Given a directed graph includes n vertices (from 1 to n) and m edges. Given q queries of two integers a and b. For each queries, check if there is a path from a to b which visite at most one intermediate vertex.
Input
The first line contains three integers n, m and q(n <=10^4, m, q<=10^5)
Each line in the next m lines contains two integer u and v which represented an edge from v to u.
Each line in the next m lines contains two integer a and b.
Output
Với mỗi truy vấn, xuất ra trên 1 dòng "Y" nếu có đường đi từ a đến b, ngược lại xuất ra "N"
For each query, output in one line "U" if there is a path from a to b, otherwise output "N" (without the quotes)
Example
Input: 4 4 2
1 2
1 3
2 3
3 1
1 2
1 4 Output:
Y
N
| Added by: | Ha Minh Ngoc |
| Date: | 2015-12-25 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: GOSU |