Згруповані вершини#13108

Згруповані вершини

3 секунди
256 мегабайтів

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

Непорожня множина вершин називається зв'язною, якщо для будь-яких двох вершин з усі вершини простого шляху між ними також належать .

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

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 5000) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить ціле число (1 \le n \le 5000) — кількість вершин. Кожен із наступних n - 1 рядків містить два цілі числа та (1 \le u, v \le n, u \ne v) — ребро між вершинами і . Гарантується, що ребра утворюють дерево.

Сума за всіма тестовими випадками не перевищує .

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку дерево має вершин: вершина суміжна з , і , а вершина — з , і .

  • Для x = 1 відповідь — , наприклад S = \{1, 3\}.

  • Для x = 2 відповідь — , наприклад S = \{1, 3, 4, 5\}.

  • Для x = 3 відповідь — , наприклад S = \{1, 3, 4, 5, 7\}: найбільші відстані — між і та між і , і вони дорівнюють .

  • Для x \ge 4 відповідь — , оскільки для множини всіх вершин найбільша відстань дорівнює .

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

У третьому тестовому випадку дерево — це ланцюжок 1 - 2 - 3 - 4. Для зв'язної множини з вершин ланцюжка найбільша відстань дорівнює k - 1, тому відповіді для x = 1, 2, 3, 4 — це 2, 3, 4, 4.