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