Дано дерево, состоящее из \(2n\) вершин. Напомним, что деревом называется связный неориентированный граф, в котором нет циклов. На каждой вершине написано одно целое число от \(1\) до \(n\). Каждое число от \(1\) до \(n\) написано ровно на двух различных вершинах. У каждой вершины также есть стоимость — вершина \(i\) стоит \(2^i\).
Требуется выбрать в дереве такое подмножество вершин, что:
- подмножество связно; то есть, из каждой вершины подмножества можно добраться до любой другой вершины подмножества, проходя только через вершины подмножества;
- каждое число от \(1\) до \(n\) написано хотя бы на одной вершине подмножества.
Среди всех таких подмножеств требуется найти такое, что суммарная стоимость вершин в нем минимальна. Обратите внимание, что не требуется минимизировать количество вершин в подмножестве.
Выходные данные
В первой строке выведите одно целое число \(k\) — количество вершин в подмножестве.
Во второй строке выведите \(k\) различных целых чисел от \(1\) до \(2n\) — номера вершин в выбранном подмножестве. Вершины можно выводить в произвольном порядке.
Примечание
На данных изображениях нарисованы ответы на первые два примера. В скобках около номеров вершин подписаны числа, написанные на них.
В первом примере есть такие валидные подмножества: \([2, 4, 5]\) (стоимость равна \(2^2 + 2^4 + 2^5 = 52\)), \([2, 4, 5, 6]\) (стоимость равна \(116\)), \([1, 6, 3]\) (стоимость равна \(74\)), \([2, 6, 3]\) (стоимость равна \(76\)) и многие другие.
Во втором примере стоимость подмножества \([4, 6, 3, 1]\) равна \(90\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1 3 2 3 2
4 2
1 6
6 2
6 3
2 5
|
3
2 4 5
|
|
2
|
3
2 3 1 3 2 1
6 4
2 4
5 2
3 6
3 1
|
4
1 3 4 6
|
|
3
|
6
5 2 3 4 6 4 2 5 6 1 1 3
10 8
2 10
12 7
4 10
5 9
6 2
1 9
3 4
12 6
11 5
4 5
|
6
2 3 4 5 8 10
|