| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 10 | 6 | 4 | 57.143% |
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 $n$ interesting locations numbered from 1ドル$ to $n$ connected by $n - 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 $m$ restaurants he would like to visit. It consists of $m$ positive integers where the $i$-th number represents an interesting location near which there is the $i$-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 $m$ pastry shops whose locations he remembers as a list of $m$ positive integers where the $i$-th number represents an interesting location near which is the $i$-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 1ドル$ and must return to it at the end of his walk.
The first line contains integers $n$ and $m$ (1ドル ≤ m ≤ n ≤ 3 \cdot 10^5$), the number of interesting locations and the number of restaurants/pastry shops, respectively.
The second line contains $m$ integers $a_i$ (1ドル ≤ a_i ≤ n,ドル $a_i \ne a_j$ for all $i \ne j$), the list of restaurants.
The third line contains $m$ integers $b_i$ (1ドル ≤ b_i ≤ n,ドル $b_i \ne b_j$ for all $i \ne j$), the list of pastry shops.
In each of the next $n - 1$ lines there are two integers $x_i$ and $y_i$ (1ドル ≤ x_i , y_i ≤ n$) - this means that there is a road between interesting locations $x_i$ and $y_i$ .
In the first line output $t,ドル the time in minutes that Mr. Malnar will have to walk to visit all restaurants and pastry shops, returning to location 1ドル$ at the end.
In the second line output 2ドルm$ integers $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 $m$ positive integers. The numbers in even positions represent pastry shops and should also form a permutation of the first $m$ positive integers.
Visiting locations in given order and returning to the starting position by taking the shortest route between each should take exactly $t$ minutes.
If there are multiple optimal orders, output any.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $n ≤ 5,円 000,ドル $m ≤ 10$ |
| 2 | 20 | $x_i = i,ドル $y_i = i + 1$ for all $i = 1, \dots , n - 1$ |
| 3 | 30 | $n ≤ 5,円 000$ |
| 4 | 40 | No additional constraints. |
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
Clarification of the first example:
Mr. Malnar first has to walk 1ドル$ minute to the only restaurant on location 2ドル,ドル then 2ドル$ minutes to the only pastry shop on location 3ドル$ and finally 1ドル$ minute back to location 1ドル$. Mr. Malnar will walk in total 1ドル + 2 + 1 = 4$ minutes.
Clarification of the second example:
Mr. Malnar visits restaurants and pastry shops in this order: restaurant at location 4ドル$ (2ドル$ min), pastry shop at location 4ドル$ (0ドル$ min), restaurant at location 6ドル$ (3ドル$ min), pastry shop at location 5ドル$ (1ドル$ min), restaurant at location 3ドル$ (1ドル$ min), pastry shop at location 9ドル$ (3ドル$ min), restaurant at location 2ドル$ (3ドル$ min), pastry shop at location 8ドル$ (3ドル$ min). After eating an ice cream at a pastry shop on location 8ドル$ he returns to location 1ドル$ (2ドル$ min). Mr. Malnar walks in total 2ドル + 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 7ドル$ (6ドル$ min), pastry shop at location 9ドル$ (2ドル$ min), restaurant at location 8ドル$ (1ドル$ min), pastry shop at location 10ドル$ (2ドル$ min), restaurant at location 6ドル$ (4ドル$ min), pastry shop at location 4ドル$ (2ドル$ min), restaurant at location 5ドル$ (1ドル$ min), pastry shop at location 2ドル$ (3ドル$ min), restaurant at location 3ドル$ (1ドル$ min), pastry shop at location 1ドル$ (2ドル$ min). After eating his last ice cream, he is already at location 1ドル$ so he doesn’t move. Mr. Malnar walks in total 24ドル$ minutes.