Антон посадил в своём саду дерево. Напоминаем, что дерево — это связный неориентированный граф, не содержащий циклов.
Вскоре дерево выросло. Каждая из его n вершин оказалась покрашена либо в чёрный, либо в белый цвет. Однако, Антону не нравятся разноцветные деревья, и поэтому он решил покрасить дерево так, чтобы оно было либо полностью белым, либо полностью чёрным.
Для изменения цвета вершин дерева Антону доступна только одна операция, обозначим её как paint(v), где v — некоторая вершина дерева. Эта операция перекрашивает в противоположный цвет все такие вершины u, что на кратчайшем пути от u до v все вершины покрашены в один цвет (при этом сами вершины u и v также учитываются). Например, дерево
после применения операции paint(3) станет следующим:
Антону стало интересно, за какое минимальное количество операций покраски ему удастся сделать так, чтобы дерево стало покрашено в один цвет. Помогите ему найти это число!
Выходные данные
В единственной строке выходных данных выведите единственное число — минимальное количество операций покраски, которое необходимо Антону, чтобы дерево стало либо полностью белым, либо полностью черным.
Примечание
В первом примере дерево такое же, как и на рисунке в условии. Если применить к нему сначала операцию paint(3), потом операцию paint(6), то оно будет полностью покрашено в черный цвет, поэтому ответ — 2.
Во втором примере дерево уже и так полностью покрашено в белый цвет, и к нему не придется применять ни одной операции покраски, поэтому ответ — 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11
|
2
|
|
2
|
4
0 0 0 0
1 2
2 3
3 4
|
0
|