F. Санта-Клаусы и чемпионат по футболу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Древляндии n городов, соединенных между собой n - 1 дорогой так, что из каждого города можно по дорогам добраться до любого другого. В следующем году в Древляндии пройдет чемпионат по футболу среди команд, состоящих из Санта-Клаусов. Всего в чемпионате примут участие 2k команд из 2k различных городов.

На первом этапе команды разобьются на k пар, каждая пара сыграет два матча: один в городе первой команды из пары, другой — в городе второй команды из пары. Таким образом, в каждом из 2k городов участников будет проведен ровно один матч. Однако как разбить команды на пары, пока не решено.

Перед организаторами также стоит задача определить, в каких городах расселить участников на время чемпионата. Организаторы хотят поселить команды в как можно меньшее число городов, чтобы Санта-Клаусы побольше общались друг с другом и обменивались опытом.

Никакая из команд не хочет чересчур много передвигаться во время турнира, поэтому если команда будет играть в городах u и v, то жить она хочет в городе, лежащем на кратчайшем пути из u в v (в том числе, возможно, в городе u или городе v). Также команды из одной пары необходимо расселить в одном городе.

Таким образом, организаторы турнира хотят разбить 2k команд на пары и расселить участников по минимально возможному числу m городов так, чтобы команды из одной пары жили в одном городе, и чтобы для каждой команды город, в котором она будет жить во время турнира, лежал на кратчайшем пути между городами, в которых она будет играть.

Входные данные

В первой строке заданы два целых числа n и k (2 ≤ n ≤ 2·105, 2 ≤ 2k ≤ n) — количество городов в Древляндии и количество пар команд в турнире.

Следующие n - 1 строк задают описание дорог в Древляндии, каждая из них содержит два целых числа a, b (1 ≤ a, b ≤ n, a ≠ b), что значит, что города a и b соединены очередной дорогой. Гарантируется, что из любого города можно добраться в любой другой по дорогам.

Следующая строка содержит 2k различных целых чисел c1, c2, ..., c2k (1 ≤ ci ≤ n), где ci — город, из которого команда номер i. Все эти числа различны.

Выходные данные

В первой строке выведите целое число m — минимальное количество городов, по которым можно расселить участников.

Во второй строке выведите m различных чисел чисел d1, d2, ..., dm (1 ≤ di ≤ n) — номера городов, в которых будут жить участники.

Далее выведите k строк. В j-й из них выведите 3 числа uj, vj, xj, где uj и vj — города, в которых будет играть j-я пара, а xj — номер города, в котором будут жить команды этой пары. Каждое из чисел c1, c2, ..., c2k должно встретиться среди чисел uj и vj ровно один раз. Каждое из чисел xj должно принадлежать множеству {d1, d2, ..., dm}.

Если оптимальных ответов несколько, выведите любой из них.

Пример
Входные данные
6 2
1 2
1 3
2 4
2 5
3 6
2 5 4 6
Выходные данные
1
2
5 4 2
6 2 2
Примечание

В первом тесте из условия можно расселить всех участников в один город с номером 2. Разбить на пары можно любым образом, при этом все условия всегда будут выполнены, т. к. город 2 лежит на кратчайшем пути между любой парой городов из множества {2, 4, 5, 6}.