Александр и Бабин живут на заброшенном острове. Из развлечений у них есть только деревья, камни и бомбы (не спрашивайте откуда). Им очень скучно, и они хотят сыграть в игру. Александр предложил сыграть в «Сапёр», а Бабин — в «Ним». В качестве компромисса они решили сыграть в Нимсапёр!
Не имея выбора, в качестве игрового поля, ребята выбрали дерево. Напомним, что деревом называется связный неориентированный граф без циклов.
В рамках общей игры Александр начинает играть в подыгру «Сапёр». Изначально, ни одна из вершин дерева не содержит бомб. В свой ход Александр выбирает любую вершину без бомбы и закладывает в неё бомбу. После этого в каждую вершину, не содержащую бомбу, кладётся количество камней, равное числу бомб в соседних с ней вершинах.
Бабин может прервать Александра после любого его хода. Как только это происходит, они начинают играть в «Ним» с получившимися кучками камней, причём Бабин ходит первым.
Если Бабин не прерывает Александра, Александр делает следующий ход (ставит ещё одну бомбу), после чего кучки камней обновляются, и так далее, пока Бабин не начнёт игру в «Ним».
Игрок, который не может сделать ход в «Ним», проигрывает.
Бабин очень хочет выиграть, поэтому он прервёт Александра в самый ранний возможный момент, когда сможет гарантировать свою победу.
Александр, хорошо понимая, что не может выиграть в этой игре, решил вместо этого максимизировать удовольствие, поэтому он хочет заложить как можно больше бомб, прежде чем Бабин начнёт игру в «Ним». Пожалуйста, помогите Александру найти максимальное количество бомб, которое он может заложить!
Напомним, что в игре «Ним» первый игрок выигрывает тогда и только тогда, когда побитовый 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$$$) — рёбра дерева. Гарантируется, что эти рёбра действительно образуют дерево.
В единственной строке выведите одно число — максимальное количество бомб, которое можно заложить.
| Группа | Баллы | Доп. ограничения | Необходимые группы |
| 1 | 8 | $$$n \le 8$$$ | – |
| 2 | 11 | $$$n \le 18$$$ | 1 |
| 3 | 20 | $$$n \le 45$$$ | 1–2 |
| 4 | 19 | $$$n \leq 128$$$ | 1–3 |
| 5 | 18 | $$$n \leq 243$$$ | 1–4 |
| 6 | 20 | Степени всех вершин $$$\le 3$$$ | – |
| 7 | 4 | – | 1–6 |
31 21 3
2
91 22 33 44 55 66 75 88 9
5
137 67 57 47 37 27 11 122 113 104 95 86 13
8
| Название |
|---|


