問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフ $G$ が与えられます。$i=1,2,...,M$ について、$i$ 番目の辺は頂点 $u_i$ と $v_i$ を結んでいます。
長さ $N$ の数列 $A = (A_1, …, A_N)$ が存在し，はじめ全ての要素は $0$ です。
以下の操作を考えます。

• $G$ から辺を $1$ つ選び、端点をそれぞれ $x,y$ とする。$A_x$ を $(A_x + 1)$ $\rm{mod}$ $K$ に、$A_y$ を $(A_y+1)$ $\rm{mod}$ $K$ に置き換える。ここで $a$ $\rm{mod} $ $b$ は $a$ を $b$ で割った余りを表す。

操作を $0$ 回以上行った後、最終的に数列 $A$ を与えられた数列 $B$ に一致させることは可能かどうかを判定してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

• $1 \leq T \leq 2×10^5$
• $1 \leq N \leq 2×10^5$
• $N-1 \leq M \leq 2×10^5$
• $1 \leq K \leq 10^9$
• $1 \leq u_i,v_i \leq N$
• $0 \leq B_i < K$
• 与えられるグラフは単純
• 入力はすべて整数
• $1$ つの入力ファイルにおいて、$N$ の総和、$M$ の総和はどちらも $2×10^5$ を超えない。

入力は以下の形式で標準入力から与えられます。

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

各ケースは以下の形式で与えられます。

$N$ $M$ $K$  
$u_1$ $v_1$  
$u_2$ $v_2$  
$\vdots$  
$u_M$ $v_M$    
$B_1$ $B_2$ $ ... $ $B_N$

出力

$T$ 行出力してください。
$i$ 行目は $i$ 個目のテストケースについて、 $A$ を $B$ に一致させることができる場合は Yes を，そうでない場合は No を出力してください。

出力

$A$ を $B$ に一致させることができる場合は Yes を，そうでない場合は No を出力せよ。
最後に改行してください。

サンプル

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

Yes
No