题目背景

译自 COCI 2023/2024 Contest #3 T4「Restorani」

题目描述

来到塞格德，Malnar 先生像通常一样，必须了解当地文化，品尝所有传统餐点、特色美食和当地饮料。

我们可以把塞格德想象成由 $n - 1$ 条双向道路连接的 $n$ 个景点，这些景点的编号从 $1$ 到 $n$。这样，每一对景点之间都有一条路径。令人惊奇的是，Malnar 先生走过每条道路正好需要一分钟。在景点行走的时间可以忽略不计。

Malnar 先生有一份他想去的 $m$ 家餐厅的清单。它由 $m$ 个正整数组成，其中第 $i$ 个数表示第 $i$ 个餐厅在哪个景点附近。

一个问题是 Malnar 先生在餐厅用餐后，必须马上去甜品店吃冰淇淋。另一个问题是，他拒绝两次光顾同一家甜品店。

幸运的是他有备而来，因为他知道 $m$ 家甜品店，这些甜品店的位置是由 $m$ 个正整数组成的列表，其中第 $i$ 个数字代表第 $i$ 家甜品店在这个景点附近。

Malnar 先生旅途劳累，不想走更多的路，因此他请你计算一下他需要走多少路，并提供去餐厅和甜品店的顺序，这样他就可以在没有帮助的情况下穿梭于餐厅和甜品店之间了。

Malnar 先生目前在景点 $1$，并且必须在最后回到景点 $1$。

输入格式

第一行包含整数 $n$ 和 $m\ (1\le m\le n\le 3\cdot 10^5)$，分别表示景点个数和餐厅/甜品店个数。

第二行包含 $m$ 个整数 $a_i\ (1\le a_i\le n,\forall i\neq j,a_i\neq a_j)$，表示餐厅清单。

第二行包含 $m$ 个整数 $b_i\ (1\le b_i\le n,\forall i\neq j,b_i\neq b_j)$，表示甜品店清单。

接下来 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i\ (1\le x_i,y_i\le n)$，表示景点 $x_i$ 和 $y_i$ 之间有一条道路。

输出格式

第一行输出 $t$，表示 Malnar 先生为了去所有餐厅和甜品店，并最后返回景点 $1$ 的最短用时。

第二行输出 $2m$ 个整数 $v_i$，表示去餐厅和甜品店的顺序。

在奇数位置的数表示餐馆，这些数必须组成前 $m$ 个正整数的排列。在偶数位置的数表示甜品店，这些数也必须组成前 $m$ 个正整数的排列。

按上述顺序去景点并返回开始位置所经历的时间必须为最短时间 $t$。

如果有多个最优顺序，输出任意一个均可。

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

提示

样例解释 1

Malnar 先生首先走一分钟前往唯一在景点 $2$ 的餐厅，然后走两分钟到唯一在景点 $3$ 的甜品店，然后花一分钟走回景点 $1$。Malnar 先生总共会花 $1+2+1=4$ 分钟。

样例解释 2

Malnar 先生按如下顺序去餐厅和甜品店：在景点 $4$ 的餐厅（$2$ 分钟），在景点 $4$ 的甜品店（$0$ 分钟），在景点 $6$ 的餐厅（$3$ 分钟），在景点 $5$ 的甜品店（$1$ 分钟），在景点 $3$ 的餐厅（$1$ 分钟），在景点 $9$ 的甜品店（$3$ 分钟），在景点 $2$ 的餐厅（$3$ 分钟），在景点 $8$ 的甜品店（$3$ 分钟）。在景点 $8$ 处的甜品店吃完冰淇淋后，他返回景点 $1$（$2$ 分钟）。Malnar 先生一共走了 $2+0+3+1+1+3+3+3+2=18$ 分钟。

样例解释 3

Malnar 先生按如下顺序去餐厅和甜品店：在景点 $7$ 的餐厅（$6$ 分钟），在景点 $9$ 的甜品店（$2$ 分钟），在景点 $8$ 的餐厅（$1$ 分钟），在景点 $10$ 的甜品店（$2$ 分钟），在景点 $6$ 的餐厅（$4$ 分钟），在景点 $4$ 的甜品店（$2$ 分钟），在景点 $5$ 的餐厅（$1$ 分钟），在景点 $2$ 的甜品店（$3$ 分钟），在景点 $3$ 的餐厅（$1$ 分钟），在景点 $1$ 的甜品店（$2$ 分钟）。在吃完最后的冰淇淋后，他已经在景点 $1$ 所以他不会移动。Malnar 先生一共走了 $24$ 分钟。

子任务

子任务编号	附加限制	分值
$1$	$n\le 5\ 000,m\le 10$	$18$
$2$	$\forall i=1,\ldots,n-1,x_i=i,y_i=i+1$
$3$	$n\le 5\ 000$	$27$
$4$	无附加限制	$37$