CF1932G.Moving Platforms

There is a game where you need to move through a labyrinth. The labyrinth consists of $n$ platforms, connected by $m$ passages.

Each platform is at some level $l_i$, an integer number from $0$ to $H - 1$. In a single step, if you are currently on platform $i$, you can stay on it, or move to another platform $j$. To move to platform $j$ they have to be connected by the passage, and their levels have to be the same, namely $l_i = l_j$.

After each step, the levels of all platforms change. The new level of platform $i$ is calculated as $l'_i = (l_i + s_i) \bmod H$, for all $i$.

You start on platform $1$. Find the minimum number of steps you need to get to platform $n$.

有一个游戏，你需要穿越一座迷宫。该迷宫由 $n$ 个平台组成，平台之间通过 $m$ 条通道相连。

每个平台位于某个层级 $l_i$，其值为从 $0$ 到 $H - 1$ 的整数。在单步操作中，若你当前位于平台 $i$，你可以选择停留在该平台，或移动到另一平台 $j$。要移动到平台 $j$，必须满足：平台 $i$ 与平台 $j$ 之间存在一条通道，并且它们的层级相同，即 $l_i = l_j$。

每步操作结束后，所有平台的层级都会发生变化。平台 $i$ 的新层级按如下公式计算：$l'_i = (l_i + s_i) \bmod H$，对所有 $i$ 均成立。

你从平台 $1$ 出发。求到达平台 $n$ 所需的最少步数。

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains three integers $n$, $m$, and $H$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le H \le 10^9$).

The second line contains $n$ integers $l_i$, the initial level of each platform ($0 \le l_i \le H-1$).

The third line contains $n$ integers $s_i$, the change of level for each platform ($0 \le s_i \le H-1$).

Next $m$ lines contain a description of the passages. Each passage is described as a pair of integers — the platforms, connected by the passage. There is at most one passage connecting each pair of platforms, and there is no passage connecting a platform to itself.

The sum of $n$ for all tests does not exceed $10^5$, the sum of $m$ for all tests does not exceed $10^5$.

输入的第一行包含一个整数 $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$。

For each test case, print a single integer, the minimum number of steps needed to get from platform $1$ to platform $n$.

If it is impossible to get to platform $n$, print $-1$.

对于每个测试用例，输出一个整数，表示从平台 $1$ 到达平台 $n$ 所需的最少步数。

如果无法到达平台 $n$，则输出 $-1$。

This is how levels of the platforms change, and what actions we need to perform in the first example.

Platform 1

Platform 2

Platform 3

Action

Step 1

1

9

4

Stay on the platform 1

Step 2

3

2

4

Stay on the platform 1

Step 3

5

5

4

Move to the platform 2

Step 4

7

8

4

Stay on the platform 2

Step 5

9

1

4

Stay on the platform 2

Step 6

1

4

4

Move to the platform 3

平台层级的变化方式，以及第一个示例中我们需要执行的操作如下所示：

平台 1

平台 2

平台 3

操作

第 1 步

1

9

4

停留在平台 1

第 2 步

3

2

4

停留在平台 1

第 3 步

5

5

4

移动到平台 2

第 4 步

7

8

4

停留在平台 2

第 5 步

9

1

4

停留在平台 2

第 6 步

1

4

4

移动到平台 3