Problem Description

Coming to Szeged, Mr. Malnar, as usual, must familiarize himself with the local culture, taste all traditional dishes, special foods, and local beverages.

We can imagine Szeged as consisting of $n$ attractions connected by $n - 1$ bidirectional roads, with the attractions numbered from $1$ to $n$. This way, there is a path between every pair of attractions. Remarkably, it takes Mr. Malnar exactly one minute to traverse each road. The time spent moving between attractions is negligible.

Mr. Malnar has a list of $m$ restaurants he wants to visit. It consists of $m$ positive integers, where the $i$-th number indicates the attraction near which the $i$-th restaurant is located.

One issue is that after dining at a restaurant, Mr. Malnar must immediately go to an ice cream shop. Another issue is that he refuses to visit the same ice cream shop twice.

Fortunately, he is well-prepared because he knows the locations of $m$ ice cream shops, which are represented by a list of $m$ positive integers, where the $i$-th number indicates the attraction near which the $i$-th ice cream shop is located.

Mr. Malnar is tired from his journey and does not want to walk more than necessary, so he asks you to calculate the minimum time he needs to walk and provide the sequence of visiting restaurants and ice cream shops, so he can navigate between them without assistance.

Mr. Malnar is currently at attraction $1$ and must return to attraction $1$ at the end.

Input Format

The first line contains two integers $n$ and $m\ (1\le m\le n\le 3\cdot 10^5)$, representing the number of attractions and the number of restaurants/ice cream shops, respectively.

The second line contains $m$ integers $a_i\ (1\le a_i\le n, \forall i\neq j, a_i\neq a_j)$, representing the list of restaurants.

The third line contains $m$ integers $b_i\ (1\le b_i\le n, \forall i\neq j, b_i\neq b_j)$, representing the list of ice cream shops.

The next $n-1$ lines each contain two integers $x_i$ and $y_i\ (1\le x_i, y_i\le n)$, indicating that there is a road between attractions $x_i$ and $y_i$.

Output Format

The first line should output $t$, the minimum time Mr. Malnar needs to visit all restaurants and ice cream shops and return to attraction $1$.

The second line should output $2m$ integers $v_i$, representing the sequence of visiting restaurants and ice cream shops.

The numbers at odd positions represent restaurants, and these numbers must form a permutation of the first $m$ positive integers. The numbers at even positions represent ice cream shops, and these numbers must also form a permutation of the first $m$ positive integers.

The time taken to visit the attractions in the specified order and return to the starting position must be the minimum time $t$.

If there are multiple optimal sequences, output any one of them.

Sample Input and Output

Sample Input #1

3 1
2
3
1 2
1 3

Sample Output #1

4
1 1

Sample Input #2

9 4
2 3 4 6
4 5 8 9
1 2
1 3
3 4
3 5
5 6
1 7
7 8
7 9

Sample Output #2

18
3 1 4 2 2 4 1 3

Sample Input #3

10 5
3 5 6 7 8
1 2 4 9 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Sample Output #3

24
4 4 5 5 3 3 2 2 1 1

Notes/Hints

Sample Explanation 1

Mr. Malnar first walks one minute to the only restaurant at attraction $2$, then walks two minutes to the only ice cream shop at attraction $3$, and finally walks one minute back to attraction $1$. Mr. Malnar will spend a total of $1+2+1=4$ minutes.

Sample Explanation 2

Mr. Malnar visits the restaurants and ice cream shops in the following order: restaurant at attraction $4$ (2 minutes), ice cream shop at attraction $4$ (0 minutes), restaurant at attraction $6$ (3 minutes), ice cream shop at attraction $5$ (1 minute), restaurant at attraction $3$ (1 minute), ice cream shop at attraction $9$ (3 minutes), restaurant at attraction $2$ (3 minutes), ice cream shop at attraction $8$ (3 minutes). After finishing his ice cream at attraction $8$, he returns to attraction $1$ (2 minutes). Mr. Malnar walks a total of $2+0+3+1+1+3+3+3+2=18$ minutes.

Sample Explanation 3

Mr. Malnar visits the restaurants and ice cream shops in the following order: restaurant at attraction $7$ (6 minutes), ice cream shop at attraction $9$ (2 minutes), restaurant at attraction $8$ (1 minute), ice cream shop at attraction $10$ (2 minutes), restaurant at attraction $6$ (4 minutes), ice cream shop at attraction $4$ (2 minutes), restaurant at attraction $5$ (1 minute), ice cream shop at attraction $2$ (3 minutes), restaurant at attraction $3$ (1 minute), ice cream shop at attraction $1$ (2 minutes). After finishing his last ice cream, he is already at attraction $1$ so he does not move. Mr. Malnar walks a total of $24$ minutes.

Subtasks

见题面 Input 部分

见题面 Output 部分