В Древляндии n городов, соединенных между собой n - 1 дорогой так, что из каждого города можно по дорогам добраться до любого другого. В следующем году в Древляндии пройдет чемпионат по футболу среди команд, состоящих из Санта-Клаусов. Всего в чемпионате примут участие 2k команд из 2k различных городов.
На первом этапе команды разобьются на k пар, каждая пара сыграет два матча: один в городе первой команды из пары, другой — в городе второй команды из пары. Таким образом, в каждом из 2k городов участников будет проведен ровно один матч. Однако как разбить команды на пары, пока не решено.
Перед организаторами также стоит задача определить, в каких городах расселить участников на время чемпионата. Организаторы хотят поселить команды в как можно меньшее число городов, чтобы Санта-Клаусы побольше общались друг с другом и обменивались опытом.
Никакая из команд не хочет чересчур много передвигаться во время турнира, поэтому если команда будет играть в городах u и v, то жить она хочет в городе, лежащем на кратчайшем пути из u в v (в том числе, возможно, в городе u или городе v). Также команды из одной пары необходимо расселить в одном городе.
Таким образом, организаторы турнира хотят разбить 2k команд на пары и расселить участников по минимально возможному числу m городов так, чтобы команды из одной пары жили в одном городе, и чтобы для каждой команды город, в котором она будет жить во время турнира, лежал на кратчайшем пути между городами, в которых она будет играть.
Выходные данные
В первой строке выведите целое число 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}.
Если оптимальных ответов несколько, выведите любой из них.
Примечание
В первом тесте из условия можно расселить всех участников в один город с номером 2. Разбить на пары можно любым образом, при этом все условия всегда будут выполнены, т. к. город 2 лежит на кратчайшем пути между любой парой городов из множества {2, 4, 5, 6}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
1 2
1 3
2 4
2 5
3 6
2 5 4 6
|
1
2
5 4 2
6 2 2
|