P10226 [COCI 2023/2024 #3] Restorani

**译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T4「[Restorani](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

来到塞格德，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 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$ | $18$ | | $3$ | $n\le 5\ 000$ | $27$ | | $4$ | 无附加限制 | $37$ |