Незвичайне лісовідновлення

Обмеження: 5 сек., 512 МіБ

Володимир став дуже занепокоєний через проблему стрімкого зменшення кількості дерев у світі, і вирішив спробувати її вирішити за допомогою лісовідновлення.

Лісовідновлення — це процес посадки дерев для вирощування лісу, як правило, на місці вирубаного лісу. Як не дивно, люди, що займаються теорією графів (тобто такі, як Володимир), мають інше уявлення про те, як створити ліс, а саме — зрубати дерево!

Дерево — це граф з \(N\) вершин, з’єднаних \(N - 1\) ребрами. Нехай \(u\) — вершина в дереві \(U\), яка має ступінь не менше 2 (тобто безпосередньо з’єднана принаймні з 2 іншими вершинами в \(U\)). Якщо ми видалимо \(u\) з \(U\), то отримаємо два або більше роз’єднаних (менших) дерева, або, як кажуть в теорії графів, ліс. У цій задачі ми будемо досліджувати незвичайне лісоутворення, яке вирішив використати Володимир.

Нехай \(V(S)\) — множина вершин дерева \(S\), а \(V(T)\) — множина вершин дерева \(T\). Дерево \(S\) і дерево \(T\) ідентичні, якщо існує бієкція \(V(S) \overset{f}{\longleftrightarrow} V(T)\) така, що для всіх пар вершин \((s_j, s_i)\) у \(V(S)\) \(s_j\) та \(s_i\) з’єднані ребром у \(S\) тоді і тільки тоді, коли вершини \(f(s_i)\) і \(f(s_j)\) з’єднані ребром у \(T\). Зауважимо, що \(f(s) = t\) означає, що вершині \(s\) у \(S\) відповідає вершина \(t\) у \(T\).

Ми називаємо вершину \(u\) в дереві \(U\) хорошою точкою розрізу тоді і тільки тоді, коли видалення \(u\) з \(U\) призводить до утворення двох або більше роз’єднаних дерев, і всі ці роз’єднані дерева попарно ідентичні.

Володимир був настільки занепокоєний вищеописаною проблемою, що одразу побіг шукати інвесторів для її вирішення і повністю забув про те, що для них необхідно презентувати хоча б якийсь спосіб перевірки доцільності проведення роботи, а тому він вас дуже просить розв’язати цю проблему за нього.

Ваша задача - за заданим деревом \(U\) визначити, чи існує в ньому хороша точка розрізу. Якщо така точка існує, то виведіть максимальну кількість роз’єднаних дерев, які можна отримати, видаливши рівно одну хорошу точку розрізу.

Блоки тестів

• Блок 1: 15 балів, дерево є лінійним (тобто має дві кінцеві вершини або, іншими словами, має вигляд звичайного ланцюга вершин).

• Блок 2: 50 балів, дерево є бінарним (тобто кожна вершина має не більше ніж 2 дітей).

• Блок 3: 35 балів, без додаткових обмежень.

Вхідні дані

В першому рядку задано єдине ціле число \(N\) — кількість вершин у заданому дереві.

В наступних \(N-1\) рядках задано по два цілих числа \(a_i\) та \(b_i\), які задають ребро \((a_i, b_i)\) у заданому дереві. Гарантується, що кожні дві вершини пов’язані між собою певною послідовністю ребер дерева.

Вихідні дані

В єдиному рядку виведіть одне число, яке позначає максимальну кількість роз’єднаних дерев, яку можна отримати, видаливши рівно 1 хорошу точку розрізу, або виведіть -1, якщо такої точки не існує.

Обмеження

\(3 \leq N \leq 4000\)

\(1 \leq a_i, b_i \leq N\)

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
13 1 2 1 3 1 4 2 5 5 6 2 7 3 8 3 9 9 10 4 11 11 12 4 13	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 1 2 1 3 2 4 3 5 3 6	-1

Примітки

У першому прикладі розглянемо наступне дерево, що складається з 13 вузлів:

У цьому дереві існує рівно одна хороша точка розрізу, а саме вершина 1. Зауважте, що видаливши вершину 1, ми отримаємо три однакових дерева (у даному випадку лінійні графи), тобто {6, 5, 2, 7}, {8, 3, 9, 10} і {12, 11, 4, 13}, які на рисунку позначено відповідно \(A\), \(B\) і \(C\).

• Бієкція між \(A\) та \(B\): \(f(6) = 8\), \(f(5) = 3\), \(f(2) = 9\), \(f(7) = 10\)

• Бієкція між \(A\) та \(C\): \(f(6) = 12\), \(f(5) = 11\), \(f(2) = 4\), \(f(7) = 13\)

• Бієкція між \(B\) та \(C\): \(f(8) = 12\), \(f(3) = 11\), \(f(9) = 4\), \(f(10) = 13\)

Очевидно, існують й інші бієкції для цих дерев.

У другому прикладі не існує хорошої точки розрізу.