4163 - 竞速飞车

题目描述

在一个激烈的竞速飞车游戏中,赛道由 N 个编号为 1N 的赛道点组成,这些赛道点之间通过 M单向加速车道相连,第 i 条车道从赛道点 u_i 通往赛道点 v_i

选手从起点赛道点 S 出发,目标是到达并停靠在终点赛道点 T

比赛规则规定:每使用一次加速包,飞车必须连续不间断地通过恰好 3 条加速车道(即连续完成 3 次移动),中途不能刹车或停留。只有当一次加速包使用完毕后,飞车恰好停在终点 T 时,才算成功抵达。(如果从某个赛道点出发,使用一次加速包,无法使得飞车连续不间断地通过恰好 3 条加速车道,那么本次加速包无法使用)

如果在某次加速包使用过程中(即第 1 条或第 2 条车道后)经过了 T,但没有在第 3 条车道结束时停在 T,则不算抵达,必须继续使用加速包。

请你计算:选手最少需要使用多少次加速包,才能从 S 恰好停在 T。如果无论使用多少次都无法达成,则输出 -1

输入

第一行包含两个整数 NM

接下来 M 行,每行两个整数 u_i v_i,表示一条从 u_iv_i 的单向加速车道。

最后一行包含两个整数 S T,表示起点和终点赛道点。

输出

输出一行一个整数,如果可以按要求到达,输出最少需要的加速包使用次数;如果无法到达,输出 -1

样例

输入

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

输出

2

输入

3 3
1 2
2 3
3 1
1 2

输出

-1

输入

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

输出

2
说明

样例输入 4

12 26
1 2
2 1
2 3
3 2
3 4
4 3
4 5
5 4
5 6
6 5
6 7
7 6
7 8
8 7
8 9
9 8
9 10
10 9
10 11
11 10
11 12
12 11
1 3
3 5
5 7
7 12
1 12

样例输出 4

2

样例说明 1

一种最优方案如下:
第一次使用加速包:1 → 2 → 3 → 4(停在 4)
第二次使用加速包:4 → 1 → 2 → 3(恰好在第 3 步停在 3)
共使用 2 次加速包,是最少次数。

样例说明 2

无论使用多少次加速包,最终只能回到赛道点 1,无法在某次正好完成 3 步后停在 2,因此输出 -1

数据范围

测试点编号NM
1 \sim 3 \le 10 \le 10
4 \sim 20 \le 10^5 \le 10^5

对于 100\% 的数据,满足 2 \le N \le 10^50 \le M \le \min(10^5, N(N-1))1 \le u_i, v_i \le Nu_i \neq v_i,每对 (u_i, v_i) 最多出现一次(无重边),1 \le S, T \le NS \neq T

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题