Андрюша каждый день с самого детства ходит через городской парк. Дорожки и полянки парка все время казались ему слишком одинаковыми, и однажды он решил украсить их и сделать разнообразными.
Парк состоит из n полянок, которые соединены между собой (n - 1) двусторонними дорожками, причем от каждой полянки можно дойти по дорожкам до любой другой. Андрюша решил на каждой полянке повесить один цветной шарик. Цвета шариков задаются целыми положительными числами, начиная с 1. Чтобы парк стал более разнообразным, Андрюша решил выбирать цвета шариков по-особенному. А именно, он хочет развесить шарики так, чтобы для любых трех попарно различных полянок a, b и c таких, что a и b соединены дорожкой, и b и c соединены дорожкой, цвета шариков на этих полянках были попарно различными.
Чтобы не тратить много денег на покупку шариков, Андрюша хочет использовать как можно меньше различных цветов. Так как Андрюша не очень силен в программировании, он просит вас помочь ему решить эту задачу.
В первой строке находится одно целое число n (3 ≤ n ≤ 2·105) — число полянок в парке.
В каждой из следующих (n - 1) строк находятся два целых числа x и y (1 ≤ x, y ≤ n) — номера двух полянок, соединенных очередной дорожкой.
Гарантируется, что от любой полянки можно добраться до любой другой по дорожкам.
В первой строке выведите одно целое число k — минимальное количество цветов, которое необходимо использовать Андрюше.
Во второй строке выведите n целых чисел, i-е из которых равняется цвету шарика, который нужно повесить на i-й полянке. Каждое из чисел должно быть в пределах от 1 до k.
3
2 3
1 3
3
1 3 2
5
2 3
5 3
4 3
1 3
5
1 3 2 5 4
5
2 1
3 2
4 3
5 4
3
1 2 3 1 2
В первом примере из условия парк состоит из трех полянок, которые последовательно соединены: 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
Иллюстрация к третьему примеру.
