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$。

限制条件

• $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 翻译