题目描述

有 $n$ 个节点。节点 $i$ 有两个权值 $A_i,P_i$，其中 $A_i$ 为正整数，$P_i$ 为非负整数。

从节点 $u$ 可以向另一个节点 $v$（$u \neq v$）发送信号，当且仅当

$$A_v \bmod A_u \le P_u.$$

给定起点 $S$ 和终点 $T$，求从 $S$ 到 $T$ 的最短路径长度，即最少经过的边数。若不可达，输出 $-1$。

$S$ 与 $T$ 允许相等；此时最短路径长度为 $0$。不同节点的 $A_i$ 或 $P_i$ 可以相同。

输入格式

第一行包含三个整数 $n,S,T$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $A_i,P_i$。

输出格式

输出最短路径长度；若无法到达，输出 $-1$。

样例

6 1 4
3 0
9 1
19 2
38 0
6 0
18 0

3

样例解释

一条最短路径为 $1 \to 2 \to 3 \to 4$。

数据规模与约定

本题采用捆绑测试。对于所有数据：

$$1 \le n \le 10^6,\ 1 \le A_i \le 10^6,\ 0 \le P_i \le 10^6,\ 1 \le S,T \le n.$$

子任务	$n \le$	$A_i \le$	特殊性质	分值	测试点数
1	$3000$	$500$	无	20	8
2	$10^5$			15	6
3		$10^5$	$P_i=0$
4			$P_i \le 2$	10	4
5			无
6	$10^6$			30	12

原题链接

原题链接