跳房子

题目描述

Ken 君非常喜欢跳房子。今天他决定在有向图 $G$ 上跳房子。

$G$ 有编号为 $1$ 到 $N$ 的 $N$ 个顶点和 $M$ 条边,第 $i$ 条边从顶点 $u_i$ 连到顶点 $v_i$。

Ken 君一开始在顶点 $S$,想通过跳房子移动到顶点 $T$。

一次跳房子是指:「从自己当前所在顶点出发的边中选 1 条,沿着这条边移动到它所连接的顶点」这个操作连续进行正好 3 次。

请回答 Ken 君能否移动到顶点 $T$,如果能,最少需要多少次跳房子才能移动到顶点 $T$。

注意:即使在跳房子操作的途中经过顶点 $T$,也不算作「移动到了顶点 $T$」。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

如果无论重复多少次跳房子都无法从顶点 $S$ 移动到顶点 $T$,则输出 $-1$。

如果能够移动,则输出移动到顶点 $T$ 所需的最少跳房子次数。

样例

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

2

第 1 次跳房子按 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$,第 2 次跳房子按 $4 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 移动,可以到达顶点 $3$,这是最少的次数。

3 3
1 2
2 3
3 1
1 2

-1

无论重复多少次跳房子,最终都会到达顶点 $1$,所以无法移动到顶点 $2$。

虽然跳房子途中可以经过顶点 $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

数据范围

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