English · Original
Chinese · Translation
Formal · Original
The country Treeland consists of _n_ cities connected with _n_ - 1 bidirectional roads in such a way that it's possible to reach every city starting from any other city using these roads. There will be a soccer championship next year, and all participants are Santa Clauses. There are exactly 2_k_ teams from 2_k_ different cities.
During the first stage all teams are divided into _k_ pairs. Teams of each pair play two games against each other: one in the hometown of the first team, and the other in the hometown of the other team. Thus, each of the 2_k_ cities holds exactly one soccer game. However, it's not decided yet how to divide teams into pairs.
It's also necessary to choose several cities to settle players in. Organizers tend to use **as few cities as possible** to settle the teams.
Nobody wants to travel too much during the championship, so if a team plays in cities _u_ and _v_, it wants to live in one of the cities on the shortest path between _u_ and _v_ (maybe, in _u_ or in _v_). There is another constraint also: the teams from one pair must live in the same city.
Summarizing, the organizers want to divide 2_k_ teams into pairs and settle them in the minimum possible number of cities _m_ in such a way that teams from each pair live in the same city which lies between their hometowns.
## Input
The first line of input contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 2·105, 2 ≤ 2_k_ ≤ _n_) — the number of cities in Treeland and the number of pairs of teams, respectively.
The following _n_ - 1 lines describe roads in Treeland: each of these lines contains two integers _a_ and _b_ (1 ≤ _a_, _b_ ≤ _n_, _a_ ≠ _b_) which mean that there is a road between cities _a_ and _b_. It's guaranteed that there is a path between any two cities.
The last line contains 2_k_ distinct integers _c_1, _c_2, ..., _c_2_k_ (1 ≤ _c__i_ ≤ _n_), where _c__i_ is the hometown of the _i_\-th team. All these numbers are distinct.
## Output
The first line of output must contain the only positive integer _m_ which should be equal to the minimum possible number of cities the teams can be settled in.
The second line should contain _m_ distinct numbers _d_1, _d_2, ..., _d__m_ (1 ≤ _d__i_ ≤ _n_) denoting the indices of the cities where the teams should be settled.
The _k_ lines should follow, the _j_\-th of them should contain 3 integers _u__j_, _v__j_ and _x__j_, where _u__j_ and _v__j_ are the hometowns of the _j_\-th pair's teams, and _x__j_ is the city they should live in during the tournament. Each of the numbers _c_1, _c_2, ..., _c_2_k_ should occur in all _u__j_'s and _v__j_'s exactly once. Each of the numbers _x__j_ should belong to {_d_1, _d_2, ..., _d__m_}.
If there are several possible answers, print any of them.
[samples]
## Note
In the first test the orginizers can settle all the teams in the city number 2. The way to divide all teams into pairs is not important, since all requirements are satisfied anyway, because the city 2 lies on the shortest path between every two cities from {2, 4, 5, 6}.
Treeland 国由 #cf_span[n] 座城市组成，这些城市通过 #cf_span[n - 1] 条双向道路连接，使得从任意一座城市都可以通过这些道路到达其他任何城市。明年将举行一场足球锦标赛，所有参赛者都是圣诞老人。共有恰好 #cf_span[2k] 支队伍，来自 #cf_span[2k] 个不同的城市。
在第一阶段，所有队伍被分成 #cf_span[k] 对。每对中的两支队伍进行两场比赛：一场在第一支队伍的家乡，另一场在第二支队伍的家乡。因此，#cf_span[2k] 座城市中的每座都将举办恰好一场足球比赛。但目前尚未决定如何将队伍配对。
同时，需要选择若干城市来安置球员。主办方希望使用尽可能少的城市来安置队伍。
为了避免在锦标赛期间长途旅行，如果一支队伍在城市 #cf_span[u] 和 #cf_span[v] 比赛，它希望居住在 #cf_span[u] 和 #cf_span[v] 之间的最短路径上的某座城市（可能就在 #cf_span[u] 或 #cf_span[v]）。还有一个约束条件：同一对的两支队伍必须居住在同一座城市。
综上所述，主办方希望将 #cf_span[2k] 支队伍配成 #cf_span[k] 对，并用最少的城市数量 #cf_span[m] 安置这些队伍，使得每对队伍居住在同一座城市，且该城市位于它们家乡之间的最短路径上。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 2·105, 2 ≤ 2k ≤ n]）——分别表示 Treeland 的城市数量和队伍对数。
接下来的 #cf_span[n - 1] 行描述了 Treeland 的道路：每行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a, b ≤ n, a ≠ b]），表示城市 #cf_span[a] 和 #cf_span[b] 之间有一条道路。保证任意两座城市之间都有路径相连。
最后一行包含 #cf_span[2k] 个互不相同的整数 #cf_span[c1, c2, ..., c2k]（#cf_span[1 ≤ ci ≤ n]），其中 #cf_span[ci] 表示第 #cf_span[i] 支队伍的家乡。所有这些数字互不相同。
输出的第一行必须包含一个正整数 #cf_span[m]，表示队伍可以被安置的最少城市数量。
第二行应包含 #cf_span[m] 个互不相同的数字 #cf_span[d1, d2, ..., dm]（#cf_span[1 ≤ di ≤ n]），表示队伍应被安置的城市编号。
接下来的 #cf_span[k] 行，第 #cf_span[j] 行应包含三个整数 #cf_span[uj], #cf_span[vj] 和 #cf_span[xj]，其中 #cf_span[uj] 和 #cf_span[vj] 是第 #cf_span[j] 对队伍的家乡，#cf_span[xj] 是他们在锦标赛期间居住的城市。每个数字 #cf_span[c1, c2, ..., c2k] 必须在所有的 #cf_span[uj] 和 #cf_span[vj] 中恰好出现一次。每个数字 #cf_span[xj] 必须属于集合 #cf_span[{d1, d2, ..., dm}]。
如果有多种可能的答案，输出任意一种即可。
在第一个测试用例中，主办方可以将所有队伍安置在城市 #cf_span[2]。队伍如何配对并不重要，因为城市 #cf_span[2] 位于集合 #cf_span[{2, 4, 5, 6}] 中任意两座城市之间的最短路径上，因此所有要求均已满足。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 2·105, 2 ≤ 2k ≤ n]）——分别表示 Treeland 的城市数量和队伍对数。接下来的 #cf_span[n - 1] 行描述了 Treeland 的道路：每行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a, b ≤ n, a ≠ b]），表示城市 #cf_span[a] 和 #cf_span[b] 之间有一条道路。保证任意两座城市之间都有路径相连。最后一行包含 #cf_span[2k] 个互不相同的整数 #cf_span[c1, c2, ..., c2k]（#cf_span[1 ≤ ci ≤ n]），其中 #cf_span[ci] 表示第 #cf_span[i] 支队伍的家乡。所有这些数字互不相同。
## Output
输出的第一行必须包含一个正整数 #cf_span[m]，表示队伍可以被安置的最少城市数量。第二行应包含 #cf_span[m] 个互不相同的数字 #cf_span[d1, d2, ..., dm]（#cf_span[1 ≤ di ≤ n]），表示队伍应被安置的城市编号。接下来的 #cf_span[k] 行，第 #cf_span[j] 行应包含三个整数 #cf_span[uj], #cf_span[vj] 和 #cf_span[xj]，其中 #cf_span[uj] 和 #cf_span[vj] 是第 #cf_span[j] 对队伍的家乡，#cf_span[xj] 是他们在锦标赛期间居住的城市。每个数字 #cf_span[c1, c2, ..., c2k] 必须在所有的 #cf_span[uj] 和 #cf_span[vj] 中恰好出现一次。每个数字 #cf_span[xj] 必须属于集合 #cf_span[{d1, d2, ..., dm}]。如果有多种可能的答案，输出任意一种即可。
[samples]
## Note
在第一个测试用例中，主办方可以将所有队伍安置在城市 #cf_span[2]。队伍如何配对并不重要，因为城市 #cf_span[2] 位于集合 #cf_span[{2, 4, 5, 6}] 中任意两座城市之间的最短路径上，因此所有要求均已满足。
**Definitions**
Let $ T = (V, E) $ be a tree with $ n $ vertices (cities) and $ n-1 $ edges (roads).
Let $ C \subseteq V $ be the set of $ 2k $ distinct cities hosting teams, with $ |C| = 2k $.
**Constraints**
1. $ 2 \leq n \leq 2 \cdot 10^5 $, $ 2 \leq 2k \leq n $
2. The graph $ T $ is a tree.
3. $ C $ contains exactly $ 2k $ distinct vertices.
**Objective**
Partition $ C $ into $ k $ unordered pairs $ \{(u_j, v_j)\}_{j=1}^k $, and assign to each pair a *settlement city* $ x_j \in V $ such that:
- $ x_j $ lies on the unique simple path between $ u_j $ and $ v_j $ in $ T $,
- All teams in pair $ j $ reside in the same city $ x_j $,
- The total number of distinct settlement cities $ m = |\{x_1, \dots, x_k\}| $ is minimized.
Output:
- The minimal $ m $,
- A set $ D = \{d_1, \dots, d_m\} \subseteq V $ of settlement cities,
- A pairing $ \{(u_j, v_j, x_j)\}_{j=1}^k $ satisfying the above.
API Response (JSON)
{
"problem": {
"name": "F. Santa Clauses and a Soccer Championship",
"description": {
"content": "The country Treeland consists of _n_ cities connected with _n_ - 1 bidirectional roads in such a way that it's possible to reach every city starting from any other city using these roads. There will b",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF748F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The country Treeland consists of _n_ cities connected with _n_ - 1 bidirectional roads in such a way that it's possible to reach every city starting from any other city using these roads. There will b...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Treeland 国由 #cf_span[n] 座城市组成，这些城市通过 #cf_span[n - 1] 条双向道路连接，使得从任意一座城市都可以通过这些道路到达其他任何城市。明年将举行一场足球锦标赛，所有参赛者都是圣诞老人。共有恰好 #cf_span[2k] 支队伍，来自 #cf_span[2k] 个不同的城市。\n\n在第一阶段，所有队伍被分成 #cf_span[k] 对。每对中的两支队伍进行两场...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T = (V, E) $ be a tree with $ n $ vertices (cities) and $ n-1 $ edges (roads). \nLet $ C \\subseteq V $ be the set of $ 2k $ distinct cities hosting teams, with $ |C| = 2k $. \n...",
"is_translate": false,
"language": "Formal"
}
]
}