22084번 - Организация сети 스페셜 저지다국어

В одной прогрессивной стране полным ходом идёт развитие информационных технологий! Ударными темпами были проложены магистрали, которые будут использоваться для передачи данных. Для простоты контроля за потоками данных и экономии средств на прокладку, магистрали были проложены таким образом, что данные могут дойти от любого города до любого другого единственным образом.

Однако, недостаточно лишь проложить провода, нужно также разработать алгоритмы маршрутизации. В ходе обсуждений была следующая модель маршрутизации данных: k городов объявляются ключевыми точками и каждый из них переименовывается в «Серверград-i». После этого, каждый город получает сетевой адрес. Сетевым адресом города v будет массив из k элементов, в котором i-й элемент равен количеству городов, через которые должен пройти трафик, чтобы попасть из города v в Серверград-i.

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

В первой строке задано число n (2 ≤ n ≤ 100 000) — количество городов в стране. Далее, в n - 1 строке заданы пары городов, между которыми проложена магистраль.

Выведите число k — минимальное число Серверградов, которых хватит для обеспечения корректной маршрутизации всех городов. Далее, выведите k различных целых чисел от 1 до n, где i-е число отвечает за то, какой город будет выбран в качестве Серверград-i-го.