自动驾驶

题目描述

有 $N$ 颗行星和 $M$ 条航线。行星编号为 $1$ 到 $N$，航线编号为 $1$ 到 $M$。

第 $i$ 条航线从行星 $A_i$ 单向通往行星 $B_i$。

一艘飞船可以执行下面两种操作：

• 不消耗燃料，移动到「当前行星的所有航线终点中编号最小的那颗行星」；
• 任选一条从当前行星出发的航线，移动到它的终点，消耗 $1$ 单位燃料。

请求出飞船从行星 $S$ 出发、到达行星 $T$ 最少需要消耗多少单位燃料。如果无法到达行星 $T$， 输出 $-1$。

输入格式

第一行四个整数 $N, M, S, T$，用空格隔开。

接下来 $M$ 行，第 $i$ 行两个整数 $A_i, B_i$，用空格隔开，表示第 $i$ 条航线从行星 $A_i$ 通往行星 $B_i$。

输出格式

输出一个整数，表示从行星 $S$ 到达行星 $T$ 最少需要消耗的燃料量；若无法到达，输出 $-1$。

7 10 2 1
2 5
2 4
4 2
4 3
3 1
3 5
3 6
5 6
6 1
6 7

1

样例 1 解释

按下面的顺序移动，可以从行星 $2$ 到行星 $1$，共消耗 $1$ 单位燃料：

1. 从行星 $2$ 不消耗燃料，移动到行星 $4$；
2. 从行星 $4$ 移动到行星 $3$，消耗 $1$ 单位燃料；
3. 从行星 $3$ 不消耗燃料，移动到行星 $1$。

7 10 2 7
2 5
2 4
4 2
4 3
3 1
3 5
3 6
5 6
6 1
6 7

2

样例 2 解释

按下面的顺序移动，可以从行星 $2$ 到行星 $7$，共消耗 $2$ 单位燃料：

1. 从行星 $2$ 不消耗燃料，移动到行星 $4$；
2. 从行星 $4$ 不消耗燃料，移动到行星 $2$；
3. 从行星 $2$ 移动到行星 $5$，消耗 $1$ 单位燃料；
4. 从行星 $5$ 不消耗燃料，移动到行星 $6$；
5. 从行星 $6$ 移动到行星 $7$，消耗 $1$ 单位燃料。

2 1 1 2
2 1

-1

样例 3 解释

从行星 $1$ 出发无法到达行星 $2$，所以输出 $-1$。

数据范围

对于所有测试数据，保证：

• $2 \le N \le 2 \times 10^5$；
• $1 \le M \le 2 \times 10^5$；
• $1 \le S, T \le N$，且 $S \ne T$；
• $1 \le A_i, B_i \le N$，且 $A_i \ne B_i$（$1 \le i \le M$）；
• 不同的航线可以连接同一对行星，即 $(A_i, B_i)$ 允许重复出现；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。