在一个激烈的竞速飞车游戏中,赛道由 N 个编号为 1 到 N 的赛道点组成,这些赛道点之间通过 M 条单向加速车道相连,第 i 条车道从赛道点 u_i 通往赛道点 v_i。
选手从起点赛道点 S 出发,目标是到达并停靠在终点赛道点 T。
比赛规则规定:每使用一次加速包,飞车必须连续不间断地通过恰好 3 条加速车道(即连续完成 3 次移动),中途不能刹车或停留。只有当一次加速包使用完毕后,飞车恰好停在终点 T 时,才算成功抵达。(如果从某个赛道点出发,使用一次加速包,无法使得飞车连续不间断地通过恰好 3 条加速车道,那么本次加速包无法使用)
如果在某次加速包使用过程中(即第 1 条或第 2 条车道后)经过了 T,但没有在第 3 条车道结束时停在 T,则不算抵达,必须继续使用加速包。
请你计算:选手最少需要使用多少次加速包,才能从 S 恰好停在 T。如果无论使用多少次都无法达成,则输出 -1。
第一行包含两个整数 N 和 M。
接下来 M 行,每行两个整数 u_i v_i,表示一条从 u_i 到 v_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
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
2
一种最优方案如下:
第一次使用加速包:1 → 2 → 3 → 4(停在 4)
第二次使用加速包:4 → 1 → 2 → 3(恰好在第 3 步停在 3)
共使用 2 次加速包,是最少次数。
无论使用多少次加速包,最终只能回到赛道点 1,无法在某次正好完成 3 步后停在 2,因此输出 -1。
| 测试点编号 | N | M |
|---|---|---|
| 1 \sim 3 | \le 10 | \le 10 |
| 4 \sim 20 | \le 10^5 | \le 10^5 |
对于 100\% 的数据,满足 2 \le N \le 10^5,0 \le M \le \min(10^5, N(N-1)),1 \le u_i, v_i \le N,u_i \neq v_i,每对 (u_i, v_i) 最多出现一次(无重边),1 \le S, T \le N,S \neq T。