Дерево — это неориентированный связный граф, в котором отсутствуют циклы. В этой задаче речь идет о некорневых деревьях.
Лист дерева — это вершина, которая соединена не более чем с одной другой вершиной.
Садовник Виталий вырастил дерево из \(n\) вершин. Он решил подстричь дерево. Для этого он совершает несколько операций. За одну операцию он удаляет все листья дерева.
Пример дерева. Например, рассмотрим дерево, изображённое на рисунке выше. На рисунке ниже приведён результат применения к дереву ровно одной операции.
Результат применения операции «удалить все листья». Обратите внимание на особенные случаи применения операций:
- применение операции к пустому дереву (из \(0\) вершин) не меняет его;
- применение операции к дереву из одной вершины приводит к удалению этой вершины (т. е. одна эта вершина считается листом);
- применение операции к дереву из двух вершин приводит к удалению обеих вершин (обе вершины считаются листьями).
Виталий применил к дереву последовательно \(k\) операций. Сколько вершин в нём осталось?
Выходные данные
Для каждого набора входных данных выведите в отдельной строке одно целое число — количество вершин, которое осталось в дереве после применения \(k\) операций.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе задано дерево из двух вершин. К нему применяются \(200000\) операций. Первая удаляет обе вершины, остальные операции не изменяют дерево.
В третьем наборе входных данных дано дерево из трёх вершин. В результате применения первой операции в нём остаётся всего \(1\) вершина (с номером \(2\)), в результате второй операции дерево становится пустым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14
2 200000
1 2
3 2
1 2
2 3
5 1
5 1
3 2
2 1
5 4
6 2
5 1
2 5
5 6
4 2
3 4
7 1
4 3
5 1
1 3
6 1
1 7
2 1
|
7
0
0
3
1
2
|