Медуза
У Ягеллонському університеті ми дуже любимо рослини, і тому створили безліч задач про дерева, ліси та навіть кактуси! Однак задачі про тварин не такі популярні. Сьогодні ми хочемо показати, що ми також любимо тварин.
Граф називається медузою, якщо це простий зв'язний неорієнтований граф, у якого кількість вершин дорівнює кількості ребер. Вам дано медузу J з n вершинами. Для будь-якої підмножини вершин S ⊆ J ми кажемо, що S є дивовижною підмножиною, якщо для кожної підмножини T ⊆ S існує зв'язний підграф медузи, що містить усі вершини з T і не містить жодної іншої вершини з S.
Який максимально можливий розмір дивовижної підмножини J?
Вхідні дані
Перший рядок містить кількість тестів z. Далі йдуть описи тестів.
Перший рядок кожного тесту містить одне ціле число n (3 ≤ n ≤ 10^5) — кількість вершин медузи.
Наступні n рядків містять по два цілі числа u[i], v[i] (1 ≤ u[i] ≠ v[i] ≤ n), що відповідають ребрам медузи. Гарантується, що даний граф є медузою і кожні дві вершини з'єднані не більше ніж одним ребром.
Загальна кількість вершин у всіх тестах не перевищує 10^6.
Вихідні дані
Для кожного тесту виведіть одне ціле число - максимально можливий розмір дивовижної підмножини медузи.