Посадка трави#10332
Фермер Джон вирішив засіяти травою всі свої поля. Вся ферма складається з полів, пронумерованих від до , які з'єднані n - 1 двосторонніми шляхами так, що з будь-якого поля можна дістатися до будь-якого іншого.
Фермер може використати різні типи трави на різних полях, однак прагне мінімізувати загальну кількість типів трави, оскільки більше типів означає більші витрати.
На жаль, корови на фермі стали перебірливими щодо їжі. Якщо один і той же тип трави буде посіяний на двох сусідніх полях (безпосередньо з'єднаних шляхом) або навіть на двох полях, які обидва безпосередньо з'єднані з одним і тим же полем, корови поскаржаться на одноманітність. Джону зовсім не потрібні скарги корів, зважаючи на їхню відому схильність до витівок у разі невдоволення.
Допоможіть Джону визначити мінімальну кількість типів трави, яку потрібно використати для всієї ферми.
Перший рядок містить число n~(1 \le n \le 10^5). Кожен з наступних n - 1 рядків описує шлях і містить два поля, які він з'єднує.
Виведіть мінімальну кількість типів трави, яку потрібно використати Джону.
У наведеному прикладі є поля, з'єднані лінійно. Потрібно щонайменше три типи трави. Наприклад, Джон може засіяти поля травами типів і у такому порядку: A - B - C - A.
Приклад 1