Андрюша каждый день с самого детства ходит через городской парк. Дорожки и полянки парка все время казались ему слишком одинаковыми, и однажды он решил украсить их и сделать разнообразными.
Парк состоит из n полянок, которые соединены между собой (n - 1) двусторонними дорожками, причем от каждой полянки можно дойти по дорожкам до любой другой. Андрюша решил на каждой полянке повесить один цветной шарик. Цвета шариков задаются целыми положительными числами, начиная с 1. Чтобы парк стал более разнообразным, Андрюша решил выбирать цвета шариков по-особенному. А именно, он хочет развесить шарики так, чтобы для любых трех попарно различных полянок a, b и c таких, что a и b соединены дорожкой, и b и c соединены дорожкой, цвета шариков на этих полянках были попарно различными.
Чтобы не тратить много денег на покупку шариков, Андрюша хочет использовать как можно меньше различных цветов. Так как Андрюша не очень силен в программировании, он просит вас помочь ему решить эту задачу.
Выходные данные
В первой строке выведите одно целое число k — минимальное количество цветов, которое необходимо использовать Андрюше.
Во второй строке выведите n целых чисел, i-е из которых равняется цвету шарика, который нужно повесить на i-й полянке. Каждое из чисел должно быть в пределах от 1 до k.
Примечание
В первом примере из условия парк состоит из трех полянок, которые последовательно соединены: 1 → 3 → 2. Значит, цвета шариков на каждой полянке должны быть попарно различны.
Иллюстрация к первому примеру. Во втором примере в парке можно найти следующие тройки полянок, соединенных последовательно:
- 1 → 3 → 2
- 1 → 3 → 4
- 1 → 3 → 5
- 2 → 3 → 4
- 2 → 3 → 5
- 4 → 3 → 5
Отсюда мы видим, что каждая пара полянок лежит в какой-нибудь тройке, а значит цвета шариков на всех полянках должны быть попарно различны.
Иллюстрация ко второму примеру. В третьем примере есть следующие тройки:
- 1 → 2 → 3
- 2 → 3 → 4
- 3 → 4 → 5
Это значит, что одного или двух цветов недостаточно, а для трех цветов ответ существует и приведен в примере.
Иллюстрация к третьему примеру.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3
1 3
|
3
1 3 2
|
|
2
|
5
2 3
5 3
4 3
1 3
|
5
1 3 2 5 4
|
|
3
|
5
2 1
3 2
4 3
5 4
|
3
1 2 3 1 2
|