分数: 500 点
问题陈述
肯爱 肯肯帕 (日本版跳房子)。今天,他将在有向图上发挥它 G. G 包括 N 顶点编号 1 to N,和 M 边缘。的 i从顶点开始的第一个边缘点 u_i 到顶点 v_i.
首先,Ken 站在 Vertex 上 S。他想要到达顶点 T 通过重复ken-ken-pa。在一次 ken-ken-pa 中,他恰好执行了三次以下操作:沿着从他所站立的顶点指向的一条边移动。
确定他是否可以到达顶点 T 通过重复ken-ken-pa。如果答案是肯定的,找到到达 Vertex 所需的最少 ken-ken-pa 数量 T。请注意,访问 Vertex T 位于 ken-ken-pa 中间不算到达顶点 T 通过重复 ken-ken-pa。
约束
- 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
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 : u_M v_M S T
输出
如果 Ken 无法到达顶点 T 来自顶点 S 通过重复 ken-ken-pa,打印 -1。 如果可以的话,打印到达顶点所需的最小 ken-ken-pa 数量 T.
示例输入 1
4 4 1 2 2 3 3 4 4 1 1 3
示例输出 1
2
肯可以到达顶点 3 来自顶点 1 中的两个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 数量。
示例输入 2
3 3 1 2 2 3 3 1 1 2
示例输出 2
-1
任意数量的ken-ken-pa都会将Ken带回Vertex 1,所以他无法到达顶点 2,尽管他可以在 ken-ken-pa 中间穿过它。
示例输入 3
2 0 1 2
示例输出 3
-1
顶点 S 和顶点 T 可能已断开连接。
示例输入 4
6 8 1 2 2 3 3 4 4 5 5 1 1 4 1 5 4 6 1 6
示例输出 4
2