Недавно Маленький Джон получил дерево от своей тёти, чтобы украсить свой дом. Но, как кажется, одного дерева недостаточно, чтобы украсить весь дом. У Маленького Джона появилась идея. Может быть, он сможет удалить несколько вершин из дерева. Это превратит его в большее количество деревьев! Верно? Вам дано дерево\(^{\text{∗}}\), состоящее из \(n\) вершин. Вы должны выполнить следующую операцию ровно дважды.
- Выберите вершину \(v\);
- Удалите все рёбра, соединённые с вершиной \(v\), а также саму вершину \(v\).
Вам необходимо найти максимальное количество компонент связности после выполнения операции ровно дважды.
Две вершины \(x\) и \(y\) находятся в одной компоненте связности тогда и только тогда, когда существует путь от \(x\) до \(y\). Граф с \(0\) вершинами имеет \(0\) компонент связности по определению.\(^{\text{†}}\)
Выходные данные
Для каждого теста выведите максимальное количество компонент связности в отдельной строке.
Примечание
В первом примере удаление вершины дважды сделает граф пустым. По определению количество компонент связности в графе с \(0\) вершинами равно \(0\). Поэтому ответ равен \(0\).
Во втором примере удаление двух вершин \(1\) и \(2\) оставляет \(2\) компоненты связности. Поскольку невозможно создать \(3\) компоненты связности с \(2\) вершинами, ответ равен \(2\).
В третьем примере удаление двух вершин \(1\) и \(5\) оставляет \(4\) компоненты связности, которые являются \(\left\{ 2,4\right\}\), \(\left\{ 3\right\}\), \(\left\{ 6\right\}\) и \(\left\{ 7\right\}\). Можно показать, что невозможно получить \(5\) компонент связности. Поэтому ответ равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 2
4
1 2
2 3
2 4
7
1 2
1 3
2 4
4 5
5 6
5 7
|
0
2
4
|