Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

G. Перемещающиеся платформы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть игра, в которой вам нужно перемещаться по лабиринту. Лабиринт состоит из $$$n$$$ платформ, соединенных $$$m$$$ проходами.

Каждая платформа находится на уровне $$$l_i$$$, уровни платформ — целые числа от $$$0$$$ до $$$H - 1$$$. За один шаг, если вы находитесь на платформе $$$i$$$, вы можете остаться на ней или перейти на другую платформу $$$j$$$. Чтобы перейти на платформу $$$j$$$, они должны быть соединены проходом, и их уровни должны быть одинаковыми, то есть $$$l_i = l_j$$$.

После каждого шага уровни всех платформ меняются. Новый уровень платформы $$$i$$$ вычисляется как $$$l'_i = (l_i + s_i) \bmod H$$$, для всех $$$i$$$.

Вы начинаете на платформе $$$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
Примечание

Вот как меняются уровни платформ и какие действия нам нужно выполнить в первом примере.

Платформа 1Платформа 2Платформа 3Действие
Шаг 1194Остаться на платформе 1
Шаг 2324Остаться на платформе 1
Шаг 3554Перейти на платформу 2
Шаг 4784Остаться на платформе 2
Шаг 5914Остаться на платформе 2
Шаг 6144Перейти на платформу 3