Hopscotch Addict

题目描述

Ken 喜欢 ken-ken-pa（日本版的跳房子）。今天，他将在有向图 $G$ 上玩它。 $G$ 包含编号为 $1$ 到 $N$ 的 $N$ 个顶点和 $M$ 条边。第 $i$ 条边从顶点 $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$。

输入格式

Input is given from Standard Input in the following format: $N$ $M$ $u_1$ $v_1$ : $u_M$ $v_M$ $S$ $T$

输出格式

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

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

2

3 3
1 2
2 3
3 1
1 2

-1

2 0
1 2

-1

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)$ If $i \neq j$, $(u_i, v_i) \neq (u_j, v_j)$. $1 \leq S, T \leq N$ $S \neq T$Ken 可以通过两次 ken-ken-pa 从顶点 $1$ 到达顶点 $3$，过程如下：在第一次 ken-ken-pa 中 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$，然后在第二次 ken-ken-pa 中 $4 \rightarrow 1 \rightarrow 2 \rightarrow 3$。这是到达所需的最小 ken-ken-pa 次数。
任意次数的 ken-ken-pa 都会把 Ken 带回顶点 $1$，因此他不能到达顶点 $2$，尽管他可以在一次 ken-ken-pa 的中途经过它。
顶点 $S$ 和顶点 $T$ 可能不连通。

标签: AtCoder|abc132E

来源

AtCoder|abc132E