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

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

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

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