AT_arc213_c [ARC213C] Double X

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木が $ 2 $ 個与えられ、それぞれ $ T, U $ と呼びます。 $ T $ の $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ辺です。 $ U $ の $ i $ 番目の辺は頂点 $ b_i $ と頂点 $ c_i $ を結ぶ辺です。 また、長さ $ N $ の整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 $ k = 1, 2, \dots, N $ に対して次の小問題を解いてください。 > 次の条件を満たす整数の組 $ (x_1, x_2, x_3, x_4) $ は存在しますか？また、存在する場合は条件を満たす組における $ \sum_{i=1}^4 A_{x_i} $ の最小値を求めてください。 > > - $ x_1, x_2, x_3, x_4 $ は全て相異なる。 > - $ x_1, x_2, x_3, x_4 $ は全て $ k $ でない。 > - $ 1 \leq i \lt j \leq 4 $ を満たす全ての整数 $ (i,j) $ について、 $ T $ 上の $ x_i x_j $ パスに頂点 $ k $ は載っていて、かつ $ U $ 上の $ x_i x_j $ パスにも頂点 $ k $ は載っている。 $ t $ 個のテストケースが与えられるので、それぞれについて問題を解いてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースを意味する。 > $ t $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_t $ 各テストケースでは、入力は以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ b_1 $ $ c_1 $ $ b_2 $ $ c_2 $ $ \vdots $ $ b_{N-1} $ $ c_{N-1} $

$ t $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。 各テストケースでは、小問題の答えを空白区切りで $ k=1,2,\dots,N $ の順に $ 1 $ 行に出力せよ。 小問題では、条件を満たす整数の組 $ (x_1, x_2, x_3, x_4) $ が存在しない場合は $ -1 $ を、存在する場合はそのような組における $ \sum_{i=1}^4 A_{x_i} $ の最小値を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、 $ k=1,2,3,4 $ の時は条件を満たす $ (x_1, x_2, x_3, x_4) $ は存在しません。また、 $ k=5 $ の時は $ (x_1,x_2,x_3,x_4) = (1,2,3,4) $ が条件を満たします。 ### Constraints - $ 1 \leq t \leq 10^5 $ - $ 5 \leq N \leq 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - $ 1 \leq u_i \lt v_i \leq N $ - $ 1 \leq b_i \lt c_i \leq N $ - $ T, U $ は木 - 全てのテストケースに対する $ N $ の総和は $ 10^5 $ 以下 - 入力される値は全て整数