Problem Statement

There are $N$ slimes numbered from $1$ to $N$. The color of each slime is represented by an integer between $0$ and $2K$ (inclusive), and the color of slime $i$ is $C_i$.

Currently, $M$ pairs of slimes are in a (bidirectional) friendship. Specifically, slimes $A_i$ and $B_i$ are friends ($1 \leq i \leq M$). Here, it is guaranteed that for any two slimes, one can reach the other by following friendship relations.

You can perform the following operation:

• First, choose a pair of slimes $(u,v)$ that satisfies both of the following conditions:
• Slimes $u$ and $v$ are in a friendship.
  • $(C_u - C_v) \bmod (2K+1) \geq K+1$ (here, the result of $x \bmod y$ is always in the range $[0,y-1]$).
• Then, let slime $u$ eat slime $v$. Slime $v$ disappears from the field. Also, all slimes except $u$ that were in a friendship with slime $v$ become friends with slime $u$ (if they were already friends with slime $u$, nothing happens).

Determine whether it is possible to leave only slime $1$ on the field by repeating the operation appropriately.

Solve $T$ cases for one input.

Constraints

• $1 \leq T \leq 125000$
• $2 \leq N \leq 250000$
• $N-1 \leq M \leq 250000$
• $1 \leq K \leq N$
• $0 \leq C_i \leq 2K$
• $1 \leq A_i < B_i \leq N$
• $(A_i,B_i) \neq (A_j,B_j)$ ($i \neq j$)
• For any two slimes, one can reach the other by following friendship relations.
• The sum of $N$ over the $T$ cases is at most $250000$.
• The sum of $M$ over the $T$ cases is at most $250000$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N M K
C_1 C_2 \cdots C_N
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Output $T$ lines. The $i$-th line should contain Yes if it is possible to leave only slime $1$ on the field for the $i$-th case, and No otherwise.