Background

Translated from T4 “Restorani” of COCI 2023/2024 Contest #3

Problem Description

Arriving in Szeged, Mr. Malnar, as usual, must learn about the local culture by tasting all traditional dishes, special foods, and local drinks.

We can imagine Szeged as $n$ locations connected by $n - 1$ bidirectional roads, with the locations numbered from $1$ to $n$. Thus, there is a path between every pair of locations. Surprisingly, it takes Mr. Malnar exactly one minute to walk along any road. The time spent walking within a location can be ignored.

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

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

Fortunately, he is prepared, because he knows $m$ ice cream shops, whose locations are given as a list of $m$ positive integers, where the $i$-th number indicates near which location the $i$-th ice cream shop is.

Mr. Malnar is tired of traveling and does not want to walk any extra, so he asks you to compute how much he needs to walk, and to provide the order of visiting restaurants and ice cream shops, so that he can travel between them without help.

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

Input Format

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

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

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

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 locations $x_i$ and $y_i$.

Output Format

On the first line output $t$, the minimum time Mr. Malnar needs to visit all restaurants and all ice cream shops, and finally return to location $1$.

On the second line output $2m$ integers $v_i$, describing the visiting order of restaurants and ice cream shops.

Numbers in odd positions represent restaurants, and they must form a permutation of the first $m$ positive integers. Numbers in even positions represent ice cream shops, and they must also form a permutation of the first $m$ positive integers.

Following this order of visiting the corresponding locations and returning to the starting location must yield the minimum time $t$.

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

3 1
2
3
1 2
1 3

4
1 1

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

18
3 1 4 2 2 4 1 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

24
4 4 5 5 3 3 2 2 1 1

Hint

Sample Explanation 1

Mr. Malnar first walks for one minute to the only restaurant at location $2$, then walks for two minutes to the only ice cream shop at location $3$, and then spends one minute walking back to location $1$. In total, Mr. Malnar spends $1+2+1=4$ minutes.

Sample Explanation 2

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

Sample Explanation 3

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

Subtasks

Translated by ChatGPT 5