Santa Clauses and a Soccer Championship
Contest: Technocup 2017 - Elimination Round 3
Difficulty rating: 2300
Tags: constructive algorithms, dfs and similar, graphs, trees

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 2k teams from 2k 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 2k 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 2k 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 format:
The first line of input contains two integers n and k (2 ≤ n ≤ 2·105, 2 ≤ 2k ≤ 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 2k distinct integers c1, c2, ..., c2k (1 ≤ ci ≤ n), where ci is the hometown of the i-th team. All these numbers are distinct.

Output format:
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 d1, d2, ..., dm (1 ≤ di ≤ 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 uj, vj and xj, where uj and vj are the hometowns of the j-th pair's teams, and xj is the city they should live in during the tournament. Each of the numbers c1, c2, ..., c2k should occur in all uj's and vj's exactly once. Each of the numbers xj should belong to {d1, d2, ..., dm}.

If there are several possible answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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}.

Example input:
6 2
1 2
1 3
2 4
2 5
3 6
2 5 4 6

Example output:
1
2
5 4 2
6 2 2

Editorial:
Firstly, let's prove that there exists a vertex v in the tree such that if we make it a root, all subtrees of its neighbours (which does not contain v) contain no more than k vertices in which some games are played (we call these vertices chosen further). We root the tree in some vertex root and denote f(u) the number of chosen vertices in the subtree of u. Now we need to prove that there exists vertex v such that f(v) ≥ k (then no more than k vertices outside subtree of v are chosen), but for all children to of v f(to) ≤ k holds. Assume there is no such vertex v, then each vertex u such that f(u) > k has some child u' such that f(u') > k. So we can build a sequence u0, u1, ... such that u0 = root,  ui + 1 is a child of ui and f(ui) > k. But obviously, at some point we will go to the leaf, which clearly has f(u) ≤ 1. This leads us to a contradiction.
This argument also gives us an easy way to find the desired vertex v: just calculate f(u) for all subtrees of the rooted tree and then go from the root down, always going to the child with f(ui + 1) > k, at some point we will find that such vertex does not exist — then current vertex is the one we were looking for.
We claim that the answer to the original problem is always 1, i.e. we can always choose one vertex, where all teams will live. Consider vertex v having f(to) ≤ k for all its children. We create a list of all chosen vertices, firstly we write all chosen vertices of the first child's subtree of v, then all chosen vertices of the second child's subtree, and so on. In the end, if v is chosen too, we add it to the end of the list. Now we have a list of 2k vertices a. Let's create k pairs of the form (ai, ai + k). Since for all children of v f(to) ≤ k holds, the vertices which numbers in the list differ by k can not belong to the same subtrees, and thus the shortest path between ai and ai + k passes through the vertex v.