P17757 「RSOI-3F」信号传递 / signal

题目来源：【HT-126-Div.2】核桃 CSP-S 组模拟赛

给定 $n$ 个节点，每个节点有两个正整数权值 $A_i$ 和 $P_i$。 在图上，从节点 $u$ 可以向节点 $v$（$u \neq v$）发送信号，当且仅当这两个节点的权值满足以下条件： $$A_v \bmod A_u \le P_u$$ 现在给定起点 $S$ 和终点 $T$，请你求出信号从 $S$ 传递到 $T$ 的最短路径长度（即最少经过的边数）。如果无法将信号传递到 $T$，请输出 `-1`。

第一行包含三个正整数 $n, S, T$，分别表示节点总数、起点编号和终点编号。 接下来 $n$ 行，每行包含两个非负整数 $A_i, P_i$，表示第 $i$ 个节点的权值。

输出一行一个整数，表示最短路径的长度。如果无法到达，输出 `-1`。

**【样例解释 #1】** - 节点 1 的权值为 $A_1=3, P_1=0$。可以到达满足 $A_v \bmod 3 \le 0$ 的节点，即节点 2（$9 \bmod 3 = 0$）、节点 5（$6 \bmod 3 = 0$）和节点 6。 - 节点 2 的权值为 $A_2=9, P_2=1$。可以到达满足 $A_v \bmod 9 \le 1$ 的节点，即节点 3（$19 \bmod 9 = 1 \le 1$）和节点 6。 - 节点 3 的权值为 $A_3=19, P_3=2$。可以到达满足 $A_v \bmod 19 \le 2$ 的节点，即节点 4（$38 \bmod 19 = 0 \le 2$）。 - 最短路径为 $1 \to 2 \to 3 \to 4$，经过了 3 条边，因此长度为 3。虽然节点 1 可以直接到节点 5 或 6，但它们无法进一步到达终点 4。 **【数据范围】** **本题采用捆绑测试。** 对于所有测试数据，保证： $1 \le n,A_i,P_i \le 10^6, 1 \le S, T \le n$。 | Subtask 编号 | $n\le$ | $A_i\le$ | 特殊性质 | 分值 | | ------------ | ---- | ---- | ---- | ---- | | 1 | $3000$ | $500$ | 无 | $20$ | | 2 | $10^5$ | ^ | ^ | $15$ | | 3 | ^ | $10^5$ | 保证 $P_i=0$ | $15$ | | 4 | ^ | ^ | $P_i\le 2$ |$10$ | | 5 | ^ | ^ | 无 |$10$ | | 6 | $10^6$ | $10^6$ | ^ | $30$ |