Cycle

题目描述

有一个由 $N$ 个顶点（编号为 $1$ 到 $N$）和 $M$ 条边组成的简单有向图。第 $i$ 条边 $(1 \leq i \leq M)$ 是一条从顶点 $a_i$ 指向顶点 $b_i$ 的有向边。
判断是否存在包含顶点 $1$ 的环路，如果存在，找出这些环路中边数的最小值。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$

输出格式

如果存在包含顶点 $1$ 的环路，输出这些环路中边数的最小值。否则，输出 $-1$。

3 3
1 2
2 3
3 1

3

3 2
1 2
2 3

-1

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

4

提示

$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$. 所有输入值均为整数。顶点 $1$ $\to$ 顶点 $2$ $\to$ 顶点 $3$ $\to$ 顶点 $1$ 是一条包含三个边的环路，并且这是唯一一条包含顶点 $1$ 的环路。

标签: AtCoder|abc376D

来源

AtCoder|abc376D