← 返回题目列表

AtCoder · abc306_g

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
  • If 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-th (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-st 测试用例,

  • 你不可避免地会重复访问顶点 1 \rightarrow 2 \rightarrow 1 \rightarrow \dots。 因此,你最终将到达顶点 1 移动后 10^{10^{100}} 次,所以答案是 Yes.

对于 2-nd 测试用例,

  • 你不可避免地会重复访问顶点 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow \dots。 因此,你最终将到达顶点 2 移动后 10^{10^{100}} 次,所以答案是 No.