Problem Statement

You are given a tree graph $G$ with $N$ vertices and $M(=N-1)$ edges. For $i=1,2,...,M$, the $i$-th edge connects vertices $u_i$ and $v_i$.
There is a sequence $A = (A_1, …, A_N)$ of length $N$, all of whose elements are initially $0$.
Consider the following operation.

• Choose $1$ edge from $G$, and let its endpoints be $x,y$. Replace $A_x$ with $(A_x + 1)$ $\rm{mod}$ $K$, and $A_y$ with $(A_y+1)$ $\rm{mod}$ $K$. Here, $a$ $\rm{mod} $ $b$ denotes the remainder when $a$ is divided by $b$.

Determine whether it is possible to make the sequence $A$ equal to the given sequence $B$ after performing the operation $0$ or more times.

You are given $T$ test cases; solve each of them.

Input

• $1 \leq T \leq 2×10^5$
• $1 \leq N \leq 2×10^5$
• $M = N-1$
• $1 \leq K \leq 10^9$
• $1 \leq u_i,v_i \leq N$
• $0 \leq B_i < K$
• The given graph is a tree
• All input values are integers
• In $1$ input file, the sum of $N$ does not exceed $2×10^5$.

The input is given from standard input in the following format.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$ 
$\mathrm{case}_T$

Each case is given in the following format.

$N$ $M$ $K$  
$u_1$ $v_1$  
$u_2$ $v_2$  
$\vdots$  
$u_{M}$ $v_{M}$    
$B_1$ $B_2$ $ ... $ $B_N$

Output

Print $T$ lines.
On the $i$-th line, for the $i$-th test case, print Yes if $A$ can be made equal to $B$, and No otherwise.

Output

Print Yes if $A$ can be made equal to $B$, and No otherwise.
Print a newline at the end.

Sample

2
3 2 3
1 2
2 3
2 0 1
2 1 2
1 2
1 0

Yes
No