D - Cycle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

頂点に 1 から N の番号がついた 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 は辺数が 3 の閉路で、これが頂点 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

Score : 400 points

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