题目背景

点我跳转原题提交

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

有一个迷宫，迷宫由 $n$ 个平台组成，所有平台间由 $m$ 条通道相连。

每个平台都在某个高度 $l_i$ 上， $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$。

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

6
-1
52

提示

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