103763: [Atcoder]ABC376 D - Cycle

Problem Statement

There is a simple directed graph with $N$ vertices numbered from $1$ to $N$ and $M$ edges. The $i$-th edge $(1 \leq i \leq M)$ is a directed edge from vertex $a_i$ to vertex $b_i$.
Determine whether there exists a cycle that contains vertex $1$, and if it exists, find the minimum number of edges among such cycles.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq \min \left( \frac{N(N-1)}{2},\ 2 \times 10^5 \right)$
• $1 \leq a_i \leq N$
• $1 \leq b_i \leq N$
• $a_i \neq b_i$
• $(a_i, b_i) \neq (a_j, b_j)$ and $(a_i, b_i) \neq (b_j, a_j)$, if $i \neq j$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$

Output

If there exists a cycle that contains vertex $1$, print the minimum number of edges among such cycles. Otherwise, print -1.

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

3

Vertex $1$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $1$ is a cycle with three edges, and this is the only cycle that contains vertex $1$.

Sample Input 2

3 2
1 2
2 3

Sample Output 2

-1

Sample Input 3

6 9
6 1
1 5
2 6
2 1
3 6
4 2
6 4
3 5
5 4

Sample Output 3

4

问题陈述

有一个简单的有向图，包含$N$个顶点，编号从$1$到$N$，以及$M$条边。第$i$条边（$1 \leq i \leq M$）是从顶点$a_i$到顶点$b_i$的有向边。
判断是否存在包含顶点$1$的环，如果存在，找出这样的环中边数最少的一个。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq \min \left( \frac{N(N-1)}{2},\ 2 \times 10^5 \right)$
• $1 \leq a_i \leq N$
• $1 \leq b_i \leq N$
• $a_i \neq b_i$
• 如果$i \neq j$，则$(a_i, b_i) \neq (a_j, b_j)$且$(a_i, b_i) \neq (b_j, a_j)$。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$

输出

如果存在包含顶点$1$的环，则输出这样的环中边数最少的一个。否则，输出-1。

示例输入1

3 3
1 2
2 3
3 1

示例输出1

3

顶点$1$ $\to$ 顶点$2$ $\to$ 顶点$3$ $\to$ 顶点$1$ 是一个包含三条边的环，并且这是唯一一个包含顶点$1$的环。

示例输入2

3 2
1 2
2 3

示例输出2

-1

示例输入3

6 9
6 1
1 5
2 6
2 1
3 6
4 2
6 4
3 5
5 4

示例输出3

4