Return to 1

题目描述

我们有一个有向图，包含 $N$ 个顶点和 $M$ 条边。 顶点编号为 $1$ 到 $N$，第 $i$ 条边从顶点 $U_i$ 指向顶点 $V_i$。 你当前位于顶点 $1$。 判断你是否可以通过重复以下操作 $10^{10^{100}}$ 次最终回到顶点 $1$：

选择一条从你当前所在顶点出发的边，移动到该边指向的顶点。

给定 $T$ 个测试用例，对每个测试用例求解。

输入格式

输入从标准输入按以下格式给出。 这里，$\text{test}_i$ 表示第 $i$ 个测试用例。 $T$ $\text{test}_1$ $\text{test}_2$ $\vdots$ $\text{test}_T$

每个测试用例按以下格式给出。 $N$ $M$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

输出 $T$ 行。 第 $i$ 行 $(1\leq i \leq T)$ 应包含 $Yes$，如果你在执行题目中描述的移动 $10^{10^{100}}$ 次后可以回到顶点 $1$， 否则输出 $No$。

4
2 2
1 2
2 1
3 3
1 2
2 3
3 1
7 10
1 6
6 3
1 4
5 1
7 1
4 5
2 1
4 7
2 7
4 3
7 11
1 6
6 3
1 4
5 1
7 1
4 5
2 1
4 7
2 7
4 3
3 7

Yes
No
No
Yes

提示

所有输入值均为整数。 $1\leq T \leq 2\times 10^5$ $2\leq N \leq 2\times 10^5$ $1\leq M \leq 2\times 10^5$ 所有测试用例中 $N$ 的总和至多为 $2 \times 10^5$。 所有测试用例中 $M$ 的总和至多为 $2 \times 10^5$。 $1 \leq U_i, V_i \leq N$ $U_i \neq V_i$ 若 $i\neq j$，则 $(U_i,V_i) \neq (U_j,V_j)$。对于第 1 个测试用例，

你必然重复访问顶点 $1 \rightarrow 2 \rightarrow 1 \rightarrow \dots$。 因此，在进行 $10^{10^{100}}$ 次移动后你会回到顶点 $1$，所以答案是 $Yes$。

对于第 2 个测试用例，

你必然重复访问顶点 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow \dots$。 因此，在进行 $10^{10^{100}}$ 次移动后你会到达顶点 $2$，所以答案是 $No$。

标签: AtCoder|abc306G

来源

AtCoder|abc306G