Reachability Queries

题目描述

一个有向图由 $n$ 个结点和 $m$ 条边组成。边的编号为 1,2,$\dots$,n。 你的任务是回答 $q$ 个查询，形式为“能否从结点 $a$ 到达结点 $b$？”

输入格式

第一行输入有三个整数 $n, m$ 和 $q$：结点数、边数和查询数。 接下来有 $m$ 行描述边。每行有两个不同的整数 $a$ 和 $b$：存在一条从结点 $a$ 指向结点 $b$ 的边。 最后有 $q$ 行描述查询。每行由两个整数 $a$ 和 $b$ 组成：“能否从结点 $a$ 到达结点 $b$？”

输出格式

对每个查询输出答案：要么 "YES" 要么 "NO"。

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

YES
NO
YES

提示

$1 \le n \le 5 \cdot 10^4$ $1 \le m,q \le 10^5$

标签: CSES2143|先进技术

来源

CSES2143|先进技术