← 返回题目列表

Codeforces · 1932/G

G. 移动平台

中文机器翻译题面 查看原题

有一款游戏,你需要穿过迷宫。迷宫由 $$$n$$$ 平台组成,通过 $$$m$$$ 通道连接。

每个平台都处于某个级别 $$$l_i$$$,是从 $$$0$$$ 到 $$$H - 1$$$ 的整数。只需一步,如果您当前在平台 $$$i$$$ 上,您可以留在该平台上,或者转移到另一个平台 $$$j$$$。要移动到平台$$$j$$$,它们必须通过通道连接,并且它们的级别必须相同,即$$$l_i = l_j$$$。

每一步之后,所有平台的级别都会发生变化。对于所有 $$$i$$$,平台 $$$i$$$ 的新级别计算如下:$$$l'_i = (l_i + s_i) \bmod H$$$。

您从平台 $$$1$$$ 开始。找出到达平台 $$$n$$$ 所需的最少步数。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$H$$$ ($$$2 \le n \le 10^5$$$、$$$1 \le m \le 10^5$$$、$$$1 \le H \le 10^9$$$)。

第二行包含$$$n$$$整数$$$l_i$$$,每个平台的初始级别($$$0 \le l_i \le H-1$$$)。

第三行包含$$$n$$$整数$$$s_i$$$,每个平台的级别变化($$$0 \le s_i \le H-1$$$)。

接下来的 $$$m$$$ 行包含段落的描述。每个通道都被描述为一对整数——由通道连接的平台。每对平台之间至多有一条通道连接,并且没有通道将平台与其自身连接。

所有测试的 $$$n$$$ 总和不超过 $$$10^5$$$,所有测试的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数,即从平台 $$$1$$$ 到平台 $$$n$$$ 所需的最小步骤数。

如果无法到达平台$$$n$$$,则打印$$$-1$$$。

示例

输入 #1

3
3 3 10
1 9 4
2 3 0
1 2
3 2
1 3
2 1 10
1 2
4 6
1 2
8 7 25
22 14 5 3 10 14 11 1
9 5 4 10 7 16 18 18
2 8
6 3
3 5
7 5
2 6
1 4
4 7

输出 #1

6
-1
52

注意

这就是平台级别的变化方式,以及我们在第一个示例中需要执行的操作。

平台 1 平台 2 平台 3 操作步骤 1194 留在平台 1 步骤 2324 留在平台 1 步骤 3554 移至平台 2 步骤 4784 留在平台 2 步骤 5914 留在平台 2 步骤 6144 移至平台 3