题目描述

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

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

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

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

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

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

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

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

输入格式

第一行包含整数 $n$ 和 $m$（$1 \le m \le n \le 3 \times 10^5$），分别表示：

• $n$：景点个数；
• $m$：餐厅和甜品店的个数（餐厅、甜品店各 $m$ 家）。

第二行包含 $m$ 个整数 $a_i$（$1 \le a_i \le n$，$\forall i \neq j, a_i \neq a_j$），表示餐厅清单：第 $i$ 家餐厅位于景点 $a_i$，所有餐厅位置互不相同。

第三行包含 $m$ 个整数 $b_i$（$1 \le b_i \le n$，$\forall i \neq j, b_i \neq b_j$），表示甜品店清单：第 $i$ 家甜品店位于景点 $b_i$，所有甜品店位置互不相同。

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

输出格式

第一行输出 $t$，表示 Malnar 先生的最短用时（单位：分钟）。

第二行输出 $2m$ 个整数 $v_1, v_2, \ldots, v_{2m}$，表示行程顺序，需满足：

1. 奇数位置（$v_1, v_3, \ldots, v_{2m-1}$）是餐厅编号的排列（$1 \sim m$ 各出现一次）；
2. 偶数位置（$v_2, v_4, \ldots, v_{2m}$）是甜品店编号的排列（$1 \sim m$ 各出现一次）；
3. 行程路线为：景点 $1$ → 餐厅 $v_1$ 所在景点 → 甜品店 $v_2$ 所在景点 → 餐厅 $v_3$ 所在景点 → $\ldots$ → 甜品店 $v_{2m}$ 所在景点 → 景点 $1$，总用时为 $t$（最短可能）。

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

样例 1

输入

3 1
2
3
1 2
1 3

输出

4
1 1

样例解释

• 行程路线：景点 $1$ → 餐厅 $1$（景点 $2$，用时 $1$ 分钟）→ 甜品店 $1$（景点 $3$，用时 $2$ 分钟）→ 景点 $1$（用时 $1$ 分钟）。
• 总用时：$1 + 2 + 1 = 4$ 分钟，符合输出。

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

样例解释

• 行程顺序对应的景点路线： 景点 $1$ → 餐厅 $3$（景点 $4$，$2$ 分钟）→ 甜品店 $1$（景点 $4$，$0$ 分钟）→ 餐厅 $4$（景点 $6$，$3$ 分钟）→ 甜品店 $2$（景点 $5$，$1$ 分钟）→ 餐厅 $2$（景点 $3$，$1$ 分钟）→ 甜品店 $4$（景点 $9$，$3$ 分钟）→ 餐厅 $1$（景点 $2$，$3$ 分钟）→ 甜品店 $3$（景点 $8$，$3$ 分钟）→ 景点 $1$（$2$ 分钟）。
• 总用时：$2+0+3+1+1+3+3+3+2 = 18$ 分钟，符合输出。

样例 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$ → 餐厅 $4$（景点 $7$，$6$ 分钟）→ 甜品店 $4$（景点 $9$，$2$ 分钟）→ 餐厅 $5$（景点 $8$，$1$ 分钟）→ 甜品店 $5$（景点 $10$，$2$ 分钟）→ 餐厅 $3$（景点 $6$，$4$ 分钟）→ 甜品店 $3$（景点 $4$，$2$ 分钟）→ 餐厅 $2$（景点 $5$，$1$ 分钟）→ 甜品店 $2$（景点 $2$，$3$ 分钟）→ 餐厅 $1$（景点 $3$，$1$ 分钟）→ 甜品店 $1$（景点 $1$，$2$ 分钟）→ 景点 $1$（$0$ 分钟）。
• 总用时：$6+2+1+2+4+2+1+3+1+2 = 24$ 分钟，符合输出。

数据范围与提示

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
1	$n \le 5000, m \le 10$	18
2	$\forall i=1,\ldots,n-1, x_i=i, y_i=i+1$（景点构成一条链）
3	$n \le 5000$	27
4	无附加限制	37

评分说明

• 如果程序输出的第一行（最短用时 $t$）正确，但第二行（行程顺序）不符合要求，可在对应测试点获得 $30\%$ 的分数。
• 子任务得分取该子任务下所有测试点的最低分。