Description

教授 Pang 正沉迷于一款名为《Elden Ring》的游戏，其中的世界是一个包含 $n$ 个顶点（从 $1$ 到 $n$ 编号）和 $m$ 条无向边的连通图。玩家从顶点 $1$ 开始，穿越世界去击败位于顶点 $n$ 的神。

然而，这并不简单。对于除顶点 $1$ 以外的任何顶点 $i$，都有一个等级为 $l_i$ 的 Boss，玩家以等级 $l_1$ 开始游戏。每天，玩家可以从顶点 $1$ 前往任意顶点 $i$ 并挑战那里的 Boss。如果玩家当前的等级高于 Boss，Boss 将被消灭（失效），玩家的等级将增加 $A$。注意，经过一个有活跃 Boss 的顶点是被禁止的。（换句话说，教授 Pang 可以从顶点 $1$ 前往顶点 $i$，如果在图中存在一条从顶点 $1$ 到顶点 $i$ 的路径，使得该路径上的每个顶点（除了顶点 $i$）都没有活跃的 Boss。）同时，每天开始时，世界上所有剩余的 Boss 的等级都会增加 $B$。

要完成游戏的通关，你需要击败位于顶点 $n$ 的 Boss（Elden Beast）。给定世界的信息，教授 Pang 想知道他至少需要多少天才能做到这一点。

玩家每天只能挑战一个 Boss。

Input Format

第一行包含一个整数 $T~(1 \le T \le 10^5)$，表示测试用例的数量。

对于每个测试用例，第一行包含四个整数 $n, m, A, B~(2\leq n\leq 2\times 10^5, 1 \le m, A, B\le 2\times 10^5)$。接下来的 $m$ 行中，每行包含两个整数 $a_i, b_i~(1 \le a_i, b_i \le n)$，表示第 $i$ 条无向边的两个端点。最后一行包含 $n$ 个整数 $l_i~(1 \le l_i \le 2 \times 10^5)$，表示玩家和上述 Boss 的初始等级。

保证所有测试用例的 $n$ 之和不超过 $10^6$，$m$ 之和不超过 $10^6$。

Output Format

对于每个测试用例，输出一行包含一个整数，表示教授 Pang 完成游戏所需的最少天数。如果无法完成，请输出 $-1$。

2
5 4 5 8
1 2
1 3
1 4
4 5
15 1 1 1 1
5 4 10 5
1 2
1 3
1 4
4 5
10 4 4 4 19

2
4

Hint

题面翻译由 ChatGPT-4o 提供。