回到 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 \le i \le T)$:若可以按题面所述移动 $10^{10^{100}}$ 次后最终位于顶点 $1$,输出 Yes,否则输出 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。

数据范围

• 所有输入值都是整数。
• $1 \le T \le 2 \times 10^5$
• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• 所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。
• 所有测试用例的 $M$ 之和不超过 $2 \times 10^5$。
• $1 \le U_i, V_i \le N$
• $U_i \neq V_i$
• 若 $i \neq j$,则 $(U_i,V_i) \neq (U_j,V_j)$。