配点 : $500$ 点

問題文

$N$ 個の頂点 $1,2,\ldots,N$ からなる木 $T$ と正の整数 $c_1,c_2,\ldots,c_N$ が与えられます。 $i(1 \leq i \leq N-1)$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ をつなぐ辺です。

$T$ の各頂点に正の整数を書き込んだとき、以下のようにしてスコアを計算します。

• 各辺に、$2$ つの端点に書き込まれた整数のうち小さい方を書き込む。
• 各辺に書き込まれた整数の総和をスコアとする。

$T$ の各頂点に $c_1,c_2,\ldots,c_N$ を $1$ つずつ書き込んだときのスコアの最大値を求め、 それを達成する正の整数の書き込み方を $1$ つ構成してください。

$c_1,c_2,\ldots,c_N$ に複数回現れる整数があるときは、 その整数はその回数だけ使わなければならないことに注意してください。

制約

• $1 \leq N \leq 10000$
• $1 \leq a_i,b_i \leq N$
• $1 \leq c_i \leq 10^5$
• 与えられるグラフは木である

入力

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

$N$

$a_1$ $b_1$

$:$

$a_{N-1}$ $b_{N-1}$

$c_1$ $\ldots$ $c_N$

出力

次の形式で出力せよ。

$M$

$d_1$ $\ldots$ $d_N$

$M$ はスコアの最大値を表す。 $d_i$ は頂点 $i$ に書き込むべき整数を表す。 $d_1,d_2,\ldots,d_N$ は $c_1,c_2,\ldots,c_N$ の並べ替えでなければならない。

最大のスコアを達成する方法が複数個あるときは、 そのうちのどれを出力してもよい。

5
1 2
2 3
3 4
4 5
1 2 3 4 5

10
1 2 3 4 5

頂点 $1,2,3,4,5$ にそれぞれ $1,2,3,4,5$ を書き込むと、 $4$ つの辺にはそれぞれ $1,2,3,4$ が書き込まれるので、スコアは $10$ になります。

これが最大のスコアです。

5
1 2
1 3
1 4
1 5
3141 59 26 53 59

197
59 26 3141 59 53

$c_1,c_2,\ldots,c_N$ は互いに異なるとは限りません。