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