Наступило время, когда Фермер Джон садит траву на всех своих полях.
Имеется \(N\) полей (\(1 \leq N \leq 10^5\)), последовательно пронумерованных
\(1 \ldots N\) и удобно соединенных \(N-1\) двунаправленными дорожками
таким образом, что из каждого поля можно добраться до каждого с помощью
некоторой последовательности дорожек.
ФД может посадить на любом поле траву любого типа, но он хочет
минимизировать количество типов травы, которые он использует.
К несчастью, его коровы переборчивы, и будут недовольны, если
два соседних поля (непосредственно соединённых одной дорожкой) или даже
два почти соседних поля (оба непосредственно присоединены к общему полю)
будут засеяны травой одного типа.
Помогите ФД определить минимальное количество типов травы, которое ему
требуется, чтобы не было недовольных коров.
ФОРМАТ ВВОДА (файл planting.in):
Первая строка ввода содержит \(N\). Каждая из последующих \(N-1\) строк
описывает дорожку в терминах двух полей, которые она соединяет.
ФОРМАТ ВЫВОДА (файл planting.out):
Выведите минимальное количество типов травы, которое ФД должен использовать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
4 3
2 3
|
3
|