题目描述

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph $G$. $G$ consists of $N$ vertices numbered $1$ to $N$, and $M$ edges. The $i$-th edge points from Vertex $u_i$ to Vertex $v_i$.

First, Ken stands on Vertex $S$. He wants to reach Vertex $T$ by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex $T$ by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex $T$. Note that visiting Vertex $T$ in the middle of a ken-ken-pa does not count as reaching Vertex $T$ by repeating ken-ken-pa.

Ken 喜欢_ken-ken-pa_（日语版跳房子）。今天，他要在有向图 $G$ 上玩这个游戏。 $G$ 由 $N$ 个顶点（编号为 $1$ 至 $N$ ）和 $M$ 条边组成。其中 $i$ -th 边指向顶点 $u_i$ 和顶点 $v_i$ 。

首先，Ken 站在顶点 $S$ 上。他希望通过重复 ken-ken-pa 到达顶点 $T$ 。在一次 ken-ken-pa 中，他恰好做了以下三次：沿着从他所站顶点指向的边走。

判断他是否能通过重复 ken-ken-pa 到达顶点 $T$ 。如果答案是肯定的，求到达顶点 $T$ 所需的最少 ken-ken-pa 次数。注意，在 ken-ken-pa 过程中到达顶点 $T$ 不能算作重复 ken-ken-pa 到达顶点 $T$ 。

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$u_1$ $v_1$
$:$
$u_M$ $v_M$
$S$ $T$

输出格式

如果 Ken 无法通过重复 ken-ken-pa 从顶点 $S$ 到达顶点 $T$ ，打印 $-1$ 。如果可以，打印到达顶点 $T$ 所需的最少 ken-ken-pa 次数。

样例 #1

样例输入 #1

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

样例输出 #1

2

样例 #2

样例输入 #2

3 3
1 2
2 3
3 1
1 2

样例输出 #2

-1

样例 #3

样例输入 #3

2 0
1 2

样例输出 #3

-1

样例 #4

样例输入 #4

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

样例输出 #4

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$ 出发，Ken 可以通过两个 ken-ken-pa 到达顶点 $3$ ，具体如下：在第一个 ken-ken-pa 中有 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ ，然后在第二个 ken-ken-pa 中有 $4 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 。这是所需的最小禅杖数。

样例 $2$ 解释

任何数量的 ken-ken-pa 都会将 Ken 带回到顶点 $1$ ，因此他无法到达顶点 $2$ ，尽管他可以在 ken-ken-pa 中穿过顶点 $2$ 。

样例 $3$ 解释

顶点 $S$ 和顶点 $T$ 可能断开。