Задача Z1. Гаечка и покраска волос ≡

Условие

В один солнечный день Гаечка решила, что её образ нуждается в свежести. "Как насчёт чего-то яркого, стильного и немного эксцентричного?" — подумала она. Идея покрасить волосы в несколько цветов (разделённых на две группы — тёплые и холодные) показалась ей гениальной, но вскоре стало ясно: сделать это без проблем будет совсем непросто.

Каждый участок волос представлял собой сложную задачу. Некоторые краски могли соседствовать, а другие — вызывали странные реакции. Когда Гаечка попыталась смешать флуоресцентный оранжевый с кислотно-синим, У Дейла внезапно потемнело в глазах, Чип потерял дар речи, а Вжик нервно кружил над её головой, пока не упал в банку с краской.

Чтобы всё грамотно распланировать, Гаечка превратила свою голову в математическую задачу:

• Каждый участок волос стал вершиной графа.
• Соседствующие участки волос соединены рёбрами.

Теперь задача проста: разделить участки на две группы (по два цвета), чтобы количество рёбер, соединяющих вершины разного цвета, было максимально большим. "Это идеальный баланс между хаосом и гармонией," — решила она.

Чип взялся за рассчитать необходимое количество оксигента, Вжик помогал раскладывать краски, а Дейл продолжал предлагать добавить "немного больше блёсток".

Помогите Гаечке решить эту задачу, чтобы её новый стиль стал самым запоминающимся!

Формат входных данных

Входные данные содержат число n — количество вершин на первой строке. Далее на отдельных строках идут пары вершин, соединённых рёбрами.

Формат выходных данных

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

Примеры тестов

6
1 4
2 5
3 6

1 2 3 7 8 9

9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

1

1

1

5
1 2
1 5
2 5
2 3
3 4
4 5

1 2 4 6