#T2239. 可达性查询(Reachability Queries)

可达性查询(Reachability Queries)

链接: https://cses.fi/problemset/task/2143

板块: Advanced Techniques

时限: 1.00 s | 内存: 512 MB

题目描述

一个有向图由 nn 个节点和 mm 条边组成。边编号为 1,2,…,n1,2,\dots,n。

你的任务是回答 qq 个形如「能否从节点 aa 到达节点 bb?」的查询。

输入

第一行有三个整数 nn、mm 和 qq:节点数量、边数量与查询数量。

之后有 mm 行描述边。每行有两个不同的整数 aa 和 bb:存在一条从节点 aa 到节点 bb 的边。

最后有 qq 行描述查询。每行有两个整数 aa 和 bb:「能否从节点 aa 到达节点 bb?」

输出

对每个查询输出答案:要么是「YES」,要么是「NO」。

数据范围

1≤n≤5⋅1041 \le n \le 5 \cdot 10^4 1≤m,q≤1051 \le m,q \le 10^5

样例输入

4 4 3
1 2
2 3
3 1
4 3
1 3
1 4
4 1

样例输出

YES
NO
YES