311092: CF1932G. Moving Platforms

G. Moving Platformstime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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$.

Input

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$.

Output

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$.

ExampleInput

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

Output

6
-1
52

Note

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

题目大意：
这是一个关于移动平台的游戏，你需要通过一个由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$。你从平台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
```题目大意： 这是一个关于移动平台的游戏，你需要通过一个由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$。你从平台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 ```