分数: 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