AT_abc132_e [ABC132E] Hopscotch Addict

Ken 君非常喜欢玩“けんけんぱ”。今天，他决定在一个有向图 $G$ 上玩这个游戏。$G$ 由 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条边组成，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 Ken 君一开始站在顶点 $S$，他想通过“けんけんぱ”移动到顶点 $T$。一次“けんけんぱ”操作指的是：连续进行 $3$ 次“从当前所在顶点选择一条出边，移动到该边所连接的顶点”的操作。 请你判断 Ken 君是否能够从顶点 $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$。如果可以移动到，输出所需的最小“けんけんぱ”操作次数。

## 限制条件 - $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 翻译