题目描述
飞行棋是一款十分有趣的游戏
不过在这里, 我们只考虑如下的简化重制版本:
1. 棋盘为一个数轴 $(-∞,+∞)$
2. 如果玩家当前在 $x$, 那么下一步他可以走到 $x-1$ 或 $x+1$
3. 特殊地, 在某些位置 $a_i$ 上, 玩家可以从当前位置直接一步跳到另一个位置 $b_i$ 上
4. 玩家一开始在 $S$, 请问玩家走到 $T$ 至少需要走多少步?
输入描述
第一行三个整数 $n,S,T$ 分别表示可以直接跳跃的点数和玩家的起点与终点
接下来 $n$ 行每行2个整数 $a_i ,b_i$ 表示从 $a_i$ 可以直接一步跳到 $b_i$
输出描述
仅一行, 一个整数, 表示玩家从 $S$ 走到 $T$ 最少需要的步数
样例输入
3 1 20 1 11 10 5 6 20
样例输出
5
样例描述
最佳方案是1->11->10->5->6->20, 共5步
数据范围
$ 0 <= n <= 2 * 10^{5} $
$ 0 <= |a_i| , |b_i| , |S| , |T| <= 10^{18}$
保证 $a_i \not= a_j (i \not= j), a_i \not= b_i$
友情提示: 请注意坐标可以为负数!
子任务1:(40分)
$ 0 <= n <= 5 $
$ 0 <= |a_i| , |b_i| , |S| , |T| <= 10$
子任务2:(60分)
$ 0 <= |a_i| , |b_i| , |S| , |T| <= 2 * 10^5$
子任务3:(140分)
无其他限制
