Problem Description

Given a tree \( T \) with \( N \) vertices \( 1, 2, \ldots, N \) and positive integers \( c_1, c_2, \ldots, c_N \). The \( i \)-th edge ( \( 1 \leq i \leq N-1 \) ) connects vertex \( a_i \) and vertex \( b_i \).

When each vertex of \( T \) is filled with a positive integer, the score is calculated as follows:

• For each edge, write down the smaller of the two integers written at its endpoints.
• The score is the sum of the integers written on all edges.

Determine the maximum score when each vertex of \( T \) is filled with one of \( c_1, c_2, \ldots, c_N \), and construct one way to fill the vertices to achieve this maximum score.

Note that if an integer appears multiple times in \( c_1, c_2, \ldots, c_N \), it must be used that many times.

Input Format

The input is given from the standard input in the following format:

\( N \) \( a_1 \) \( b_1 \) \( : \) \( a_{N-1} \) \( b_{N-1} \) \( c_1 \) \( \ldots \) \( c_N \)

Output Format

Output in the following format:

\( M \) \( d_1 \) \( \ldots \) \( d_N \)

\( M \) represents the maximum score. \( d_i \) represents the integer to be written at 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 one of them can be output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

10
1 2 3 4 5

Sample Input #2

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

Sample Output #2

197
59 26 3141 59 53

Notes/Hints

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

Sample Explanation 1

Writing \( 1, 2, 3, 4, 5 \) respectively at vertices \( 1, 2, 3, 4, 5 \), the four edges will have \( 1, 2, 3, 4 \) written on them, resulting in a score of \( 10 \). This is the maximum score.

Sample Explanation 2

\( c_1, c_2, \ldots, c_N \) are not necessarily distinct.

见题面 Input 部分

见题面 Output 部分