分数: 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.