AT_abc453_f [ABC453F] Avoid Division

$ N $ 頂点の木が与えられます。 頂点は頂点 $ 1 $ 、頂点 $ 2 $ 、 $ \ldots $ 、頂点 $ N $ と番号づけられており、 $ i $ 番目 $ (1\leq i\leq N-1) $ の辺は頂点 $ U_i $ と頂点 $ V_i $ を結んでいます。 高橋君は各頂点を色 $ 1 $ 、色 $ 2 $ 、 $ \ldots $ 、色 $ K $ のうちいずれか一色で塗ります。 色 $ i $ は最大で $ C_i $ 個の頂点を塗るのに使うことができます。 次の条件をみたすように頂点を塗ることが可能か判定し、可能な場合は条件をみたす塗り方を $ 1 $ つ出力してください。 - どの辺についても、ある $ i $ $ (1\leq i\leq K) $ が存在して、その辺で木を切って得られる $ 2 $ つの部分木の両方に色 $ i $ で塗られた頂点が存在する。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ \mathrm{case}_i $ は $ i $ 個目のテストケースを表す。 各テストケースは以下の形式で与えられる。 > $ N $ $ K $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_K $

$ T $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq T) $ には、 $ i $ 個目のテストケースに対する答えを以下のように出力せよ。 条件をみたすように頂点を塗ることが不可能ならば、 $ -1 $ を $ 1 $ つだけ出力せよ。 そうでないならば、 $ N $ 個の整数 $ X_1,X_2,\ldots,X_N $ $ (1\leq X_i\leq K) $ を空白区切りで出力せよ。 ここで、 $ j=1,2,\ldots,N $ について頂点 $ i $ を色 $ X_i $ で塗った方法が条件をみたすようにせよ。

### Sample Explanation 1 $ 1 $ 個目のテストケースについて、出力例のように頂点を塗ったとします。 すなわち、頂点 $ 1 $ に色 $ 3 $ を、頂点 $ 2 $ に色 $ 2 $ を、頂点 $ 3 $ に色 $ 2 $ を、頂点 $ 4 $ に色 $ 1 $ を、頂点 $ 5 $ に色 $ 1 $ を塗ったとします。 このとき、頂点 $ 1 $ と頂点 $ 2 $ を結ぶ辺を切ったとすると、木は頂点 $ 1,3 $ からなる部分木と頂点 $ 2,4,5 $ からなる部分木に分かれますが、このときどちらにも色 $ 2 $ で塗られた頂点（頂点 $ 3 $ または頂点 $ 2 $ ）が存在します。 与えられた木を他のどの辺で切ってもそのような色が存在するため、出力例の塗り方は条件をみたしています。 $ 2 $ 個目のテストケースについて、条件をみたすように頂点を塗る方法は存在しません。 ### Constraints - $ 1\leq T\leq 10^5 $ - $ 2\leq N\leq 3\times 10^5 $ - $ 1\leq K\leq N $ - $ 1\leq U_i,V_i\leq N $ - 与えられるグラフは木である。 - $ 1\leq C_i\leq N $ - $ C_1+C_2+\cdots+C_K\geq N $ - 入力はすべて整数 - 各入力のテストケースにわたる $ N $ の総和は $ 3\times 10^5 $ を超えない。