AT_waipc_qual_c Odd Even Counters

$ 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 $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ B_1 $ $ X_1 $ $ Y_1 $ $ A_2 $ $ B_2 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ X_{N-1} $ $ Y_{N-1} $

各テストケースについて，目標を達成することが不可能なら `-1` を，可能なら必要な最小の操作回数を出力せよ．

### Sample Explanation 1 例えば， $ 1 $ 番目のテストケースについては，以下のように $ 2 $ 回の操作を行うことで目標を達成できます． - ウォーク $ (1,2,3) $ を選び， $ x_1,y_2 $ の値を $ 1 $ 増やす． - ウォーク $ (2,1) $ を選び， $ x_1 $ の値を $ 1 $ 増やす． $ 2 $ 番目と $ 3 $ 番目のテストケースでは，どうやっても目標を達成することができません． ### Constraints - $ 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 $ 以下 - 入力はすべて整数