F. Нимсапёр!
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Александр и Бабин живут на заброшенном острове. Из развлечений у них есть только деревья, камни и бомбы (не спрашивайте откуда). Им очень скучно, и они хотят сыграть в игру. Александр предложил сыграть в «Сапёр», а Бабин — в «Ним». В качестве компромисса они решили сыграть в Нимсапёр!

Не имея выбора, в качестве игрового поля, ребята выбрали дерево. Напомним, что деревом называется связный неориентированный граф без циклов.

В рамках общей игры Александр начинает играть в подыгру «Сапёр». Изначально, ни одна из вершин дерева не содержит бомб. В свой ход Александр выбирает любую вершину без бомбы и закладывает в неё бомбу. После этого в каждую вершину, не содержащую бомбу, кладётся количество камней, равное числу бомб в соседних с ней вершинах.

Бабин может прервать Александра после любого его хода. Как только это происходит, они начинают играть в «Ним» с получившимися кучками камней, причём Бабин ходит первым.

Если Бабин не прерывает Александра, Александр делает следующий ход (ставит ещё одну бомбу), после чего кучки камней обновляются, и так далее, пока Бабин не начнёт игру в «Ним».

Игрок, который не может сделать ход в «Ним», проигрывает.

Бабин очень хочет выиграть, поэтому он прервёт Александра в самый ранний возможный момент, когда сможет гарантировать свою победу.

Александр, хорошо понимая, что не может выиграть в этой игре, решил вместо этого максимизировать удовольствие, поэтому он хочет заложить как можно больше бомб, прежде чем Бабин начнёт игру в «Ним». Пожалуйста, помогите Александру найти максимальное количество бомб, которое он может заложить!

Напомним, что в игре «Ним» первый игрок выигрывает тогда и только тогда, когда побитовый XOR размеров кучек отличен от нуля.

Напомним, что XOR или Исключающим ИЛИ называется бинарная операция, которая так применяется к каждой паре битов, стоящих на одинаковых позициях в двоичных представлениях чисел, что в результате на этой позиции стоит 0, если биты равны, а иначе — 1. Например, 3 XOR 5 = 6, так как $$$3_{10}$$$ = $$$011_2$$$, $$$5_{10}$$$ = $$$101_2$$$ и потому после применения операции второй и третий бит становятся равными 1, а первый бит — 0, таким образом получается $$$110_2$$$ = $$$6_{10}$$$

Входные данные

В первой строке входных данных содержится одно целое число $$$n$$$ ($$$2 \leq n \leq 369$$$) — количество вершин в дереве.

В последующих $$$n - 1$$$ строках содержатся пары целых чисел $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — рёбра дерева. Гарантируется, что эти рёбра действительно образуют дерево.

Выходные данные

В единственной строке выведите одно число — максимальное количество бомб, которое можно заложить.

Система оценки
ГруппаБаллыДоп. ограничения Необходимые группы
18$$$n \le 8$$$–
211$$$n \le 18$$$1
320$$$n \le 45$$$1–2
419$$$n \leq 128$$$1–3
518$$$n \leq 243$$$1–4
620Степени всех вершин $$$\le 3$$$–
74–1–6
Примеры
Входные данные
3
1 2
1 3
Выходные данные
2
Входные данные
9
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
Выходные данные
5
Входные данные
13
7 6
7 5
7 4
7 3
7 2
7 1
1 12
2 11
3 10
4 9
5 8
6 13
Выходные данные
8