Байтландия — прекрасная земля, известная своими красивыми деревьями.
Миша нашел бинарное дерево с \(n\) вершинами, пронумерованными от \(1\) до \(n\). Бинарное дерево — это ациклический связный неориентированный граф, содержащий \(n\) вершин и \(n - 1\) ребер. Каждая вершина имеет степень не больше \(3\), а корнем является вершина с номером \(1\) и имеет степень не больше \(2\).
К сожалению, корень дерева был заражен. Следующий процесс происходит \(n\) раз:
- Миша либо выбирает еще не зараженную (и не удаленную) вершину и удаляет ее со всеми ребрами, имеющими конец в этой вершине, либо ничего не делает.
- Затем заражение распространяется на каждую вершину, соединенную ребром с уже зараженной вершиной (все уже зараженные вершины остаются зараженными).
Так как Мише некогда думать, скажите ему, какое максимальное количество вершин он может спасти от заражения (обратите внимание, что удаленные вершины не считаются спасенными).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
Примечание
В первом наборе входных данных единственным возможным действием является удаление вершины \(2\), после чего мы спасли \(0\) вершин.
Во втором наборе входных данных, если мы удалим вершину \(2\), мы сможем спасти вершины \(3\) и \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15
|
0
2
2
10
|