AT_abc132_e [ABC132E] Hopscotch Addict

题目描述

在一个有向图 $G$ 由 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条边组成，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

现在要从顶点 $S$ 出发到顶点 $T$。一次操作指的是：连续进行 $3$ 次“从当前所在顶点选择一条出边，移动到该边所连接的顶点”的操作。

判断是否能够从顶点 $S$ 移动到顶点 $T$，如果可以，请输出最少需要多少次操作。

如果在一次操作的中途经过顶点 $T$，也不算到达顶点 $T$，只有在完成一次完整的操作后停在顶点 $T$，才算到达。

输入格式

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

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$S$ $T$

输出格式

如果无论进行多少次操作都无法从顶点 $S$ 移动到顶点 $T$，输出 $-1$。

如果可以移动到，输出所需的最小“けんけんぱ”操作次数。

样例 1

输入

4 4
1 2
2 3
3 4
4 1
1 3

输出

2

样例 2

输入

3 3
1 2
2 3
3 1
1 2

输出

-1

样例 3

输入

2 0
1 2

输出

-1

样例 4

输入

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

输出

2

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq \min(10^5, N(N-1))$
• $1 \leq u_i, v_i \leq N\ (1 \leq i \leq M)$
• $u_i \neq v_i\ (1 \leq i \leq M)$
• 如果 $i \neq j$，则 $(u_i, v_i) \neq (u_j, v_j)$
• $1 \leq S, T \leq N$
• $S \neq T$

样例解释 1

第一次操作可以按 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ 移动，第二次操作可以按 $4 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 移动，这样就能到达顶点 $3$，这是最少的次数。

样例解释 2

无论进行多少次操作，都只能回到顶点 $1$，无法到达顶点 $2$。虽然在操作的中途可能经过顶点 $2$，但这不算到达。

样例解释 3

顶点 $S$ 和顶点 $T$ 可能是不连通的。

由 ChatGPT 4.1 翻译