Задано неориентированное дерево, состоящее из \(n\) вершин. Неориентированное дерево — это связный граф с \(n - 1\) ребром.
Ваша задача — добавить минимальное количество ребер таким образом, что длина кратчайшего пути из вершины \(1\) до любой другой вершины не превышает \(2\). Заметьте, что вы не можете добавлять петли и кратные ребра.
Выходные данные
Выведите одно целое число — минимальное количество ребер, которое необходимо добавить, чтобы длина кратчайшего пути из вершины \(1\) до любой другой вершины не превышает \(2\). Заметьте, что вы не можете добавлять петли и кратные ребра.
Примечание
Дерево, соответствующее первому тестовому примеру: 
Ответ равен \(2\), вот несколько возможных ответов: \([(1, 5), (1, 6)]\), \([(1, 4), (1, 7)]\), \([(1, 6), (1, 7)]\).
Дерево, соответствующее второму тестовому примеру: 
Ответ равен \(0\).
Дерево, соответствующее третьему тестовому примеру: 
Ответ равен \(1\), единственный способ достичь такого ответа — добавить ребро \((1, 3)\).
| № | Входные данные | Выходные данные |
|
1
|
7
1 2
2 3
2 4
4 5
4 6
5 7
|
2
|
|
2
|
7
1 2
1 3
2 4
2 5
3 6
1 7
|
0
|
|
3
|
7
1 2
2 3
3 4
3 5
3 6
3 7
|
1
|