Вам дано дерево\(^{\dagger}\). За одну зельда-операцию вы можете сделать следующее:
- Выбрать две вершины дерева \(u\) и \(v\);
- Сжать все вершины на пути от \(u\) до \(v\) в одну вершину. Другими словами, все вершины на пути от \(u\) до \(v\) будут удалены из дерева, будет создана новая вершина \(w\). Затем каждая вершина \(s\), которая имела ребро с какой-то вершиной на пути от \(u\) до \(v\), будет иметь ребро с вершиной \(w\).
Иллюстрация результата зельда-операции для вершин \(1\) и \(5\). Определите минимальное количество зельда-операций, необходимых для того, чтобы в дереве осталась только одна вершина.
\(^{\dagger}\)Дерево — это неориентированный связный граф без циклов.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество зельда-операций, необходимых для того, чтобы в дереве осталась только одна вершина.
Примечание
В первом наборе входных данных достаточно выполнить одну зельда-операцию для вершин \(2\) и \(4\).
Во втором наборе входных данных мы можем выполнить следующие зельда-операции:
- \(u = 2, v = 1\). Пусть добавленная вершина будет обозначена как \(w = 10\);
- \(u = 4, v = 9\). Пусть добавленная вершина будет обозначена как \(w = 11\);
- \(u = 8, v = 10\). После этой операции дерево состоит из одной вершины.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 2
1 3
3 4
9
3 1
3 5
3 2
5 6
6 7
7 8
7 9
6 4
7
1 2
1 3
2 4
4 5
3 6
2 7
6
1 2
1 3
1 4
4 5
2 6
|
1
3
2
2
|