G. 移动平台
每个测试点时间限制：3 秒
内存限制：512 兆字节

有一个游戏，你需要在迷宫中移动。迷宫由 $n$ 个平台组成，平台之间有 $m$ 条通道。

每个平台有一个整数等级 $l_i$，取值范围是 $0$ 到 $H-1$。
在一步操作中，如果你当前在平台 $i$ 上，你可以选择停留在这个平台，或者移动到另一个平台 $j$。
要移动到平台 $j$，需要满足：

• 平台 $i$ 和 $j$ 之间有通道相连；
• 且它们的当前等级相同，即 $l_i = l_j$。

每执行一步操作后，所有平台的等级都会发生变化。
平台 $i$ 的新等级按如下方式计算：

对所有 $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

示例解释（第一个测试用例）