← 返回题目列表

AtCoder · abc132_e

E. 跳房子瘾君子

中文机器翻译题面 查看原题

分数: 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