{"problem":{"name":"[COCI 2023/2024 #3] Restorani","description":{"content":"来到塞格德，Malnar 先生像通常一样，必须了解当地文化，品尝所有传统餐点、特色美食和当地饮料。 我们可以把塞格德想象成由 $n - 1$ 条双向道路连接的 $n$ 个景点，这些景点的编号从 $1$ 到 $n$。这样，每一对景点之间都有一条路径。令人惊奇的是，Malnar 先生走过每条道路正好需要一分钟。在景点行走的时间可以忽略不计。 Malnar 先生有一份他想去的 $m$ 家餐厅的清单。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10226"},"statements":[{"statement_type":"Markdown","content":"来到塞格德，Malnar 先生像通常一样，必须了解当地文化，品尝所有传统餐点、特色美食和当地饮料。\n\n我们可以把塞格德想象成由 $n - 1$ 条双向道路连接的 $n$ 个景点，这些景点的编号从 $1$ 到 $n$。这样，每一对景点之间都有一条路径。令人惊奇的是，Malnar 先生走过每条道路正好需要一分钟。在景点行走的时间可以忽略不计。\n\nMalnar 先生有一份他想去的 $m$ 家餐厅的清单。它由 $m$ 个正整数组成，其中第 $i$ 个数表示第 $i$ 个餐厅在哪个景点附近。\n\n一个问题是 Malnar 先生在餐厅用餐后，必须马上去甜品店吃冰淇淋。另一个问题是，他拒绝两次光顾同一家甜品店。\n\n幸运的是他有备而来，因为他知道 $m$ 家甜品店，这些甜品店的位置是由 $m$ 个正整数组成的列表，其中第 $i$ 个数字代表第 $i$ 家甜品店在这个景点附近。\n\nMalnar 先生旅途劳累，不想走更多的路，因此他请你计算一下他需要走多少路，并提供去餐厅和甜品店的顺序，这样他就可以在没有帮助的情况下穿梭于餐厅和甜品店之间了。\n\nMalnar 先生目前在景点 $1$，并且必须在最后回到景点 $1$。\n\n## Input\n\n第一行包含整数 $n$ 和 $m\\ (1\\le m\\le n\\le 3\\cdot 10^5)$，分别表示景点个数和餐厅/甜品店个数。\n\n第二行包含 $m$ 个整数 $a_i\\ (1\\le a_i\\le n,\\forall i\\neq j,a_i\\neq a_j)$，表示餐厅清单。\n\n第二行包含 $m$ 个整数 $b_i\\ (1\\le b_i\\le n,\\forall i\\neq j,b_i\\neq b_j)$，表示甜品店清单。\n\n接下来 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i\\ (1\\le x_i,y_i\\le n)$，表示景点 $x_i$ 和 $y_i$ 之间有一条道路。\n\n## Output\n\n第一行输出 $t$，表示 Malnar 先生为了去所有餐厅和甜品店，并最后返回景点 $1$ 的最短用时。\n\n第二行输出 $2m$ 个整数 $v_i$，表示去餐厅和甜品店的顺序。\n\n在奇数位置的数表示餐馆，这些数必须组成前 $m$ 个正整数的排列。在偶数位置的数表示甜品店，这些数也必须组成前 $m$ 个正整数的排列。\n\n按上述顺序去景点并返回开始位置所经历的时间必须为最短时间 $t$。\n\n如果有多个最优顺序，输出任意一个均可。\n\n[samples]\n\n## Background\n\n**译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T4「[Restorani](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**\n\n## Note\n\n### 样例解释 1\n\nMalnar 先生首先走一分钟前往唯一在景点 $2$ 的餐厅，然后走两分钟到唯一在景点 $3$ 的甜品店，然后花一分钟走回景点 $1$。Malnar 先生总共会花 $1+2+1=4$ 分钟。\n\n### 样例解释 2\n\nMalnar 先生按如下顺序去餐厅和甜品店：在景点 $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$ 分钟。\n\n### 样例解释 3\n\nMalnar 先生按如下顺序去餐厅和甜品店：在景点 $7$ 的餐厅（$6$ 分钟），在景点 $9$ 的甜品店（$2$ 分钟），在景点 $8$ 的餐厅（$1$ 分钟），在景点 $10$ 的甜品店（$2$ 分钟），在景点 $6$ 的餐厅（$4$ 分钟），在景点 $4$ 的甜品店（$2$ 分钟），在景点 $5$ 的餐厅（$1$ 分钟），在景点 $2$ 的甜品店（$3$ 分钟），在景点 $3$ 的餐厅（$1$ 分钟），在景点 $1$ 的甜品店（$2$ 分钟）。在吃完最后的冰淇淋后，他已经在景点 $1$ 所以他不会移动。Malnar 先生一共走了 $24$ 分钟。\n\n### 子任务\n\n| 子任务编号 |                附加限制                | 分值 |\n| :--------: | :------------------------------------: | :--: |\n|    $1$     |         $n\\le 5\\ 000,m\\le 10$          | $18$ |\n|    $2$     | $\\forall i=1,\\ldots,n-1,x_i=i,y_i=i+1$ | $18$ |\n|    $3$     |             $n\\le 5\\ 000$              | $27$ |\n|    $4$     |               无附加限制               | $37$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10226","tags":["2023","Special Judge","COCI（克罗地亚）"],"sample_group":[["3 1\n2\n3\n1 2\n1 3\n","4\n1 1\n"],["9 4\n2 3 4 6\n4 5 8 9\n1 2\n1 3\n3 4\n3 5\n5 6\n1 7\n7 8\n7 9\n","18\n3 1 4 2 2 4 1 3\n"],["10 5\n3 5 6 7 8\n1 2 4 9 10\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n9 10\n","24\n4 4 5 5 3 3 2 2 1 1\n"]],"created_at":"2026-03-03 11:09:25"}}