У Монокарпа есть дерево, состоящее из \(n\) вершин.
Он планирует выбрать некоторую вершину \(r\) и проделать следующие операции над каждой вершиной \(v\) от \(1\) до \(n\):
- присвоить \(d_v\) равным расстоянию от \(v\) до \(r\) (количество ребер на кратчайшем пути);
- раскрасить \(v\) в какой-нибудь цвет.
Раскраска называется красивой, если она удовлетворяет двум условиям:
- для каждой пары вершин одного цвета \((v, u)\) существует путь из \(v\) в \(u\), который посещает только вершины того же цвета;
- для каждой пары вершины одного цвета \((v, u)\), \(d_v \neq d_u\).
Обратите внимание, что Монокарп может выбирать любое количество различных цветов, которые он хочет использовать.
Для каждого использованного цвета он затем считает количество вершин этого цвета. Стоимость дерева — это минимум из этих значений.
Какая может быть наибольшая стоимость дерева?
Выходные данные
На каждый набор входных данных выведите одно целое число — наибольшая возможная стоимость дерева.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 2
2 3
3 4
5
1 2
1 3
1 4
1 5
3
1 3
3 2
7
3 2
2 5
7 5
3 1
1 6
1 4
|
4
1
3
3
|