103066: [Atcoder]ABC306 G - Return to 1

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

### 题目描述: 有一个有向图,图中有 $ N $ 个顶点和 $ M $ 条边。每个顶点被编号为从 $ 1 $ 到 $ N $,第 $ i $ 条边从顶点 $ U_i $ 指向顶点 $ V_i $。 现在你位于顶点 $1$。请判断是否可以通过以下操作恰好重复进行 $10^{10^{100}}$ 次并回到顶点 $1$: - 从当前的顶点选择一条出边,将自己移动到该边指向的顶点。 给定 $ T $ 个测试用例,请解决每个测试用例。

Output

得分: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$
  • 如果$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

加入题单

上一题 下一题 算法标签: