CF1932G Moving Platforms

有一个迷宫，迷宫由 $n$ 个平台组成，所有平台间由 $m$ 条通道相连。 每个平台都在某个高度 $l_i$ 上， $l_i$ 是一个 $0$ 到 $H - 1$ 的整数。对于每一步移动，如果你当前在平台 $i$ 上，你可以选择停留在原地或者移动到另一个平台 $j$ 上。如果要移动到平台 $j$ ，那么它们必须由通道连接，并且它们的高度必须相同，即 $l_i = l_j$。 在每一步移动之后，所有平台的高度都会改变。对于所有 $i$，平台 $i$ 的新高度计算为 $l'_i = (l_i + s_i) \bmod H$。 你的起点是平台 $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$。

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