Restorani

문제

Coming to Szeged, Mr. Malnar is, as usual, obliged to get acquainted with the local culture, and thus try all traditional meals, culinary specialties, and local drinks.

We can imagine Szeged as $nn$ interesting locations numbered from $11$ to $nn$ connected by $n-1n\; -\; 1$ bidirectional roads in such a way that there is a path using roads between every pair of interesting locations. Amazingly, Mr. Malnar needs exactly one minute to walk across each road. Time spent walking in an interesting location is negligible.

Mr. Malnar has a list of $mm$ restaurants he would like to visit. It consists of $mm$ positive integers where the $ii$-th number represents an interesting location near which there is the $ii$-th restaurant.

One problem is that Mr. Malnar must eat an ice cream in a pastry shop right after dining in a restaurant. Another problem is that he refuses to visit the same pastry shop twice.

Luckily, he came prepared as he is familiar with $mm$ pastry shops whose locations he remembers as a list of $mm$ positive integers where the $ii$-th number represents an interesting location near which is the $ii$-th pastry shop.

Mr. Malnar is tired from his travel and doesn’t want to walk more than he has to, so he asks you to calculate how much will he have to walk and offer the order of visiting restaurants and pastry shops, as he is capable of navigating between them without help.

Mr. Malnar is currently at an interesting location number $11$ and must return to it at the end of his walk.

입력

The first line contains integers $nn$ and $mm$ (1 ≤ m ≤ n ≤ 3 \cdot 10^5), the number of interesting locations and the number of restaurants/pastry shops, respectively.

The second line contains $mm$ integers $a_{i}a\_i$ (1 ≤ a_i ≤ n, $a_i\mathrm{\ne }{a}_{j}a\_i\; \backslash ne\; a\_j$ for all $i\mathrm{\ne }ji\; \backslash ne\; j$), the list of restaurants.

The third line contains $mm$ integers $b_{i}b\_i$ (1 ≤ b_i ≤ n, $b_i\mathrm{\ne }{b}_{j}b\_i\; \backslash ne\; b\_j$ for all $i\mathrm{\ne }ji\; \backslash ne\; j$), the list of pastry shops.

In each of the next $n-1n\; -\; 1$ lines there are two integers $x_{i}x\_i$ and $y_{i}y\_i$ (1 ≤ x_i , y_i ≤ n) - this means that there is a road between interesting locations $x_{i}x\_i$ and $y_{i}y\_i$ .

출력

In the first line output $tt$, the time in minutes that Mr. Malnar will have to walk to visit all restaurants and pastry shops, returning to location $11$ at the end.

In the second line output $2m2m$ integers $v_{i}v\_i$, the order of visiting restaurants and pastry shops.

The numbers in odd positions represent restaurants and should form a permutation of the first $mm$ positive integers. The numbers in even positions represent pastry shops and should also form a permutation of the first $mm$ positive integers.

Visiting locations in given order and returning to the starting position by taking the shortest route between each should take exactly $tt$ minutes.

If there are multiple optimal orders, output any.

힌트

Clarification of the first example:

Mr. Malnar first has to walk $11$ minute to the only restaurant on location $22$, then $22$ minutes to the only pastry shop on location $33$ and finally $11$ minute back to location $11$. Mr. Malnar will walk in total $1+2+1=41\; +\; 2\; +\; 1\; =\; 4$ minutes.

Clarification of the second example:

Mr. Malnar visits restaurants and pastry shops in this order: restaurant at location $44$ ($22$ min), pastry shop at location $44$ ($00$ min), restaurant at location $66$ ($33$ min), pastry shop at location $55$ ($11$ min), restaurant at location $33$ ($11$ min), pastry shop at location $99$ ($33$ min), restaurant at location $22$ ($33$ min), pastry shop at location $88$ ($33$ min). After eating an ice cream at a pastry shop on location $88$ he returns to location $11$ ($22$ min). Mr. Malnar walks in total $2+0+3+1+1+3+3+3+2=182\; +\; 0\; +\; 3\; +\; 1\; +\; 1\; +\; 3\; +\; 3\; +\; 3\; +\; 2\; =\; 18$ minutes.

Clarification of the third example:

Mr. Malnar visits restaurants and pastry shops in this order: restaurant at location $77$ ($66$ min), pastry shop at location $99$ ($22$ min), restaurant at location $88$ ($11$ min), pastry shop at location $1010$ ($22$ min), restaurant at location $66$ ($44$ min), pastry shop at location $44$ ($22$ min), restaurant at location $55$ ($11$ min), pastry shop at location $22$ ($33$ min), restaurant at location $33$ ($11$ min), pastry shop at location $11$ ($22$ min). After eating his last ice cream, he is already at location $11$ so he doesn’t move. Mr. Malnar walks in total $2424$ minutes.

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