AT_abc376_d [ABC376D] Cycle

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的简单有向图，顶点编号为 $1$ 到 $N$。第 $i$ 条边 $(1 \leq i \leq M)$ 是一条从顶点 $a_i$ 指向顶点 $b_i$ 的有向边。
请判断是否存在包含顶点 $1$ 的环路。如果存在，请输出所有包含顶点 $1$ 的环路中边数最少的环路的边数；如果不存在，请输出 $-1$。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

如果存在包含顶点 $1$ 的环路，则输出所有包含顶点 $1$ 的环路中边数最少的环路的边数。否则输出 $-1$。

输入输出样例 #1

输入 #1

3 3
1 2
2 3
3 1

输出 #1

3

输入输出样例 #2

输入 #2

3 2
1 2
2 3

输出 #2

-1

输入输出样例 #3

输入 #3

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

输出 #3

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$
• 如果 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$ 且 $(a_i, b_i) \neq (b_j, a_j)$
• 输入的所有值均为整数

样例解释 1

顶点 $1 \to$ 顶点 $2 \to$ 顶点 $3 \to$ 顶点 $1$ 构成一个边数为 $3$ 的环路，这是唯一一个包含顶点 $1$ 的环路。

由 ChatGPT 4.1 翻译