第 4 题 Restorani (restorani)

时间限制 1.0 s · 空间限制 256 MB · 146 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 restorani.in，输出文件 restorani.out。

译自 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$。

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

样例

样例 1

输入：

3 1
2
3
1 2
1 3

输出：

4
1 1

样例 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

输出：

18
3 1 4 2 2 4 1 3

样例 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 分钟），在景点 9 的餐厅（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 分钟。

子任务