AT_abc306_g [ABC306G] 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$ 行输出第 $i$ 个测试用例的答案。如果可以恰好经过 $10^{10^{100}}$ 次操作后回到顶点 $1$，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

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

输出 #1

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$ 个测试用例，

• 只能不断地 $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。

由 ChatGPT 4.1 翻译