← 返回题目列表

AtCoder · abc376_d

G. 循环

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个简单的有向图 N 顶点编号自 1 to 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
  • (a_i, b_i) \neq (a_j, b_j) 和 (a_i, b_i) \neq (b_j, a_j),如果 i \neq 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

顶点 可以从 Vertex 到达 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