

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点 M 辺の有向グラフがあります。 頂点には 1 から N までの番号が付けられていて、i 番目の辺は頂点 U_i から頂点 V_i に向かって伸びています。
あなたは今頂点 1 にいます。 以下の行動をちょうど 10^{10^{100}} 回繰り返して頂点 1 に戻ってくることが可能かどうか判定してください。
- 今いる頂点から伸びている辺を 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) 行目には、
i 番目のテストケースにおいて問題文中の行動をちょうど 10^{10^{100}} 回繰り返して頂点 1 に戻ってくることが可能ならば Yes
を、
そうでないならば 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
です。
Score : 600 points
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
.