Саше за победу на очередной олимпиаде подарили дерево\(^{\dagger}\) из \(n\) вершин. Но, вернувшись домой после празднования очередной победы, он заметил его потерю. Саша помнит, что он покрасил некоторые рёбра этого дерева. При этом он точно знает, что для любой из \(k\) пар вершин \((a_1, b_1), \ldots, (a_k, b_k)\) он покрасил хотя бы одно ребро на простом пути\(^{\ddagger}\) между вершинами \(a_i\) и \(b_i\).
Саша не помнит, сколько рёбер он точно покрасил, так что он просит вас сказать, какое минимальное количество рёбер он мог покрасить, чтобы выполнялось описанное выше условие.
\(^{\dagger}\)Деревом называется неориентированный связный граф без циклов.
\(^{\ddagger}\)Простой путь — это путь, проходящий через каждую вершину не более одного раза.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество рёбер, которое мог покрасить Саша.
Примечание
В первом наборе входных данных Саша мог покрасить только одно ребро \((1, 2)\). Тогда на простом пути между вершинами \(1\) и \(3\) и вершинами \(4\) и \(1\) будет хотя бы одно покрашенное ребро.
Во втором наборе входных данных Саша мог покрасить рёбра \((1, 6)\) и \((1, 3)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 2
2 3
2 4
2
1 3
4 1
6
1 2
3 1
6 1
5 2
4 2
3
3 1
3 6
2 6
5
1 2
2 3
3 4
4 5
4
1 2
2 3
3 4
4 5
|
1
2
4
|