103066: [Atcoder]ABC306 G - Return to 1

Problem Statement

We have a directed graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ through $N$, and the $i$-th edge goes from vertex $U_i$ to vertex $V_i$.

You are currently at vertex $1$. Determine if you can make the following move $10^{10^{100}}$ times to end up at vertex $1$:

• choose an edge going from the vertex you are currently at, and move to the vertex that the edge points at.

Given $T$ test cases, solve each of them.

Constraints

• All input values are integers.
• $1\leq T \leq 2\times 10^5$
• $2\leq N \leq 2\times 10^5$
• $1\leq M \leq 2\times 10^5$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• The sum of $M$ over all test cases is at most $2 \times 10^5$.
• $1 \leq U_i, V_i \leq N$
• $U_i \neq V_i$
• If $i\neq j$, then $(U_i,V_i) \neq (U_j,V_j)$.

Input

The input is given from Standard Input in the following format. Here, $\text{test}_i$ denotes the $i$-th test case.

$T$
$\text{test}_1$
$\text{test}_2$
$\vdots$
$\text{test}_T$

Each test case is given in the following format.

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

Output

Print $T$ lines.

The $i$-th $(1\leq i \leq T)$ line should contain Yes if you can make the move described in the problem statement $10^{10^{100}}$ times to end up at vertex $1$, and No otherwise.

Sample Input 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

Sample Output 1

Yes
No
No
Yes

For the $1$-st test case,

• You inevitably repeat visiting vertices $1 \rightarrow 2 \rightarrow 1 \rightarrow \dots$. Thus, you will end up at vertex $1$ after making the move $10^{10^{100}}$ times, so the answer is Yes.

For the $2$-nd test case,

• You inevitably repeat visiting vertices $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow \dots$. Thus, you will end up at vertex $2$ after making the move $10^{10^{100}}$ times, so the answer is No.

问题描述

我们有一个有向图，包含$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)$。

输入

输入从标准输入给出，格式如下。其中，$\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。

样例输入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个测试用例，

• 你不可避免地重复访问顶点$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。