Moving Platforms
Contest: Codeforces Round 927 (Div. 3)
Difficulty rating: 2300
Tags: graphs, math, number theory, shortest paths

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

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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

Platform 1Platform 2Platform 3ActionStep 1194Stay on the platform 1Step 2324Stay on the platform 1Step 3554Move to the platform 2Step 4784Stay on the platform 2Step 5914Stay on the platform 2Step 6144Move to the platform 3

Example input:
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

Example output:
6
-1
52

Editorial:
First, note that the event of two platforms being on the same level at a given moment does not depend on your moves. Hence, it is always optimal to get to any vertex you may need to reach the vertex $$$n$$$ as soon as possible. It means that you can simply run Dijkstra's algorithm to calculate the minimal number of moves needed to reach every vertex.
The only complication is that you need to determine for some vertices $$$u$$$, $$$v$$$ and moment $$$t$$$ what is the next moment when $$$l'_u = l'_v$$$, i.e. find minimal $$$k$$$ such that $$$k \ge t$$$ and $$$l_u + ks_u = l_v + ks_v \bmod H$$$. That can be equivalently written as $$$ l_u - l_v = k(s_v - s_u) \bmod H$$$.
$$$a = k'b \bmod H$$$ can be solved in such way:
• If $$$a$$$ is not divisible by $$$\gcd(H, b)$$$ then there is no solution.
• Otherwise, divide $$$a, b, H$$$ by $$$\gcd(H, b)$$$. Name them $$$a', b', H'$$$.
• Then $$$k' = b'^{-1}a' \bmod H$$$.
• $$$b'^{-1}$$$ can be found using extended Eucledian algorithm.
The only thing remaining is to find minimal $$$k$$$ such that $$$k' = k \bmod H'$$$ and $$$k \ge t$$$.