当前没有测试数据。

G - 返回1

分数：$600$ 分

问题描述

我们有一个有向图，有 $N$ 个顶点和 $M$ 条边。 顶点从 $1$ 到 $N$ 编号，第 $i$ 条边从顶点 $U_i$ 指向顶点 $V_i$。

你当前位于顶点 $1$。 确定你是否可以按照以下步骤进行 $10^{10^{100}}$ 次，最后到达顶点 $1$：

• 选择一个从当前顶点出发的边，移动到指向该边的顶点。

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

约束

• 所有输入值都是整数。
• $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)$

---

输入

输入以以下格式从标准输入中给出。

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

• 无论如何你都会重复访问顶点 $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。