E - 滑石迷

得分：500分

题目描述

Ken喜欢玩滑石迷游戏（日本的跳格子游戏）。今天，他将在一个有向图$G$上玩这个游戏。 $G$由$N$个编号为$1$到$N$的顶点和$M$条边组成。第$i$条边从顶点$u_i$指向顶点$v_i$。

首先，Ken站在顶点$S$上。他想通过重复滑石迷来到达顶点$T$。在一次滑石迷中，他恰好做了以下三次：沿着他所站顶点指向的边走。（意思就是每一次操作必须经过三条边）

确定是否能够通过重复滑石迷达到顶点$T$。如果答案是肯定的，找到达到顶点$T$所需的最小滑石迷次数。注意，在一次滑石迷中间路过顶点 $T$ 不算到终点。

约束

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

输入

从标准输入中以以下格式给出：

$N$ $M$

$u_1$ $v_1$

$:$

$u_M$ $v_M$

$S$ $T$

输出

如果Ken无法通过重复滑石迷从顶点$S$到达顶点$T$，则输出$-1$。 如果可以到达，输出达到顶点$T$所需的最小滑石迷次数。

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

2

Ken可以在两次滑石迷中从顶点$1$到达顶点$3$，过程如下：第一次滑石迷：$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$，第二次滑石迷：$4 \rightarrow 1 \rightarrow 2 \rightarrow 3$。这是所需要的最小滑石迷次数。

3 3
1 2
2 3
3 1
1 2

-1

无论多少次滑石迷，Ken都会回到顶点$1$，所以他不能到达顶点$2$，尽管他可以在一次滑石迷中经过顶点$2$。

2 0
1 2

-1

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

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

2