問題文

1 から N までの番号のついた N 頂点からなる無向木があります． 辺には 1 から N-1 までの番号がついており，辺 i は頂点 A_i と頂点 B_i を結んでいます．

各辺 i には 2 つのカウンター x_i,y_i があります． 最初，x_i=y_i=0 です．

あなたは今から以下の操作を 0 回以上行います．

• 木上のウォークを自由に選ぶ． より正確には，頂点列 (v_0,v_1,\ldots,v_k) (頂点 v_i,v_{i+1} は直接辺で結ばれており，ウォークの長さ k は任意) を選ぶ． 頂点 v_i,v_{i+1} を結ぶ辺を辺 e_i とする． そして，各 i=0,2,4,\ldots に対して，x_{e_i} の値を 1 増やす． 同様に，各 i=1,3,5,\ldots に対して，y_{e_i} の値を 1 増やす． なお，同じ辺が複数回登場する場合は，登場するたびにカウンターの値が増加する．

各辺には，目標とすべきカウンターの値 X_i,Y_i が定まっています． あなたの目標は，すべての辺でカウンターの値が (x_i,y_i)=(X_i,Y_i) となっている状態にすることです． 目標が達成可能かどうか判定してください． また可能な場合は，そのために必要な最小の操作回数を求めてください．

1 つの入力につき，T ケースを解いてください．

制約

• 1 \leq T \leq 125000
• 2 \leq N \leq 250000
• 1 \leq A_i,B_i \leq N
• 0 \leq X_i,Y_i \leq 10^9
• 入力されるグラフは木である
• T ケースにわたる N の総和は 250000 以下
• 入力はすべて整数

入力例 1

4
3
1 2 2 0
2 3 0 1
3
1 2 1 0
2 3 0 2
5
2 3 3 3
3 5 5 2
1 4 2 4
4 5 1 1
10
3 10 0 16306834
6 8 123600023 90587973
10 1 35502434 4326053
1 9 0 6983702
10 2 0 11702429
6 5 0 53901118
10 4 82799399 29529115
10 8 72275777 16348135
6 7 0 21602025

出力例 1

2
-1
-1
215877450

例えば，1 番目のテストケースについては，以下のように 2 回の操作を行うことで目標を達成できます．

• ウォーク (1,2,3) を選び，x_1,y_2 の値を 1 増やす．
• ウォーク (2,1) を選び，x_1 の値を 1 増やす．

2 番目と 3 番目のテストケースでは，どうやっても目標を達成することができません．