Score : $500$ points

Problem Statement

You are given a tree with $N$ vertices $1,2,\ldots,N$, and positive integers $c_1,c_2,\ldots,c_N$. The $i$-th edge in the tree $(1 \leq i \leq N-1)$ connects Vertex $a_i$ and Vertex $b_i$.

We will write a positive integer on each vertex in $T$ and calculate our score as follows:

• On each edge, write the smaller of the integers written on the two endpoints.
• Let our score be the sum of the integers written on all the edges.

Find the maximum possible score when we write each of $c_1,c_2,\ldots,c_N$ on one vertex in $T$, and show one way to achieve it. If an integer occurs multiple times in $c_1,c_2,\ldots,c_N$, we must use it that number of times.

Constraints

• $1 \leq N \leq 10000$
• $1 \leq a_i,b_i \leq N$
• $1 \leq c_i \leq 10^5$
• The given graph is a tree.

Input

Input is given from Standard Input in the following format:

$N$

$a_1$ $b_1$

$:$

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

$c_1$ $\ldots$ $c_N$

Output

Use the following format:

$M$

$d_1$ $\ldots$ $d_N$

where $M$ is the maximum possible score, and $d_i$ is the integer to write on Vertex $i$. $d_1,d_2,\ldots,d_N$ must be a permutation of $c_1,c_2,\ldots,c_N$. If there are multiple ways to achieve the maximum score, any of them will be accepted.

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

10
1 2 3 4 5

If we write $1,2,3,4,5$ on Vertex $1,2,3,4,5$, respectively, the integers written on the four edges will be $1,2,3,4$, for the score of $10$. This is the maximum possible score.

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$ may not be pairwise distinct.