Шляхи в Дереві#3103
Вам задано дерево (зв'язний граф без циклів), у якому ребра є спрямованими. Ваше завдання — додати мінімальну кількість спеціальних шляхів, щоб забезпечити можливість переходу з будь-якої вершини до будь-якої іншої. Правила для спеціальних шляхів наступні:
Спеціальний шлях складається з послідовності ребер (з дерева) і вершин.
У спеціальному шляху ребра повинні бути орієнтовані у протилежному напрямку до їхнього напрямку в дереві.
Вершина чи ребро можуть бути відвідані не більше одного разу у спеціальному шляху.
Різні спеціальні шляхи можуть мати спільні вершини або ребра.
Наприклад, на ілюстрації нижче наведено дерево. Чорні стрілки показують ребра та їх напрямок; кружечки позначають вершини. У цьому випадку потрібно два спеціальні шляхи. Один шлях — це 2-1-0 (зелена стрілка), інший — 3-1 (синя стрілка). Або замість шляху 3-1 можна додати 3-1-0. Не можна додати шлях типу 1-3 чи 0-1-2 за правилом 2, а також не можна додати 0-2 чи 2-3-0 за правилом 1.
У першому рядку задано ціле число (T \leq 30) — кількість тестів.
Кожен тест починається з рядка, який містить число (2 \leq N \leq 20000) — кількість вершин. Вершини нумеруються від до N-1. Кожен з наступних N-1 рядків містить два цілих числа (0 \leq u, v < N, u \neq v), що означає, що існує ребро з у .
Для кожного тесту виведіть номер тесту та мінімальну кількість спеціальних шляхів, необхідних для забезпечення можливості переходу між будь-якими двома вершинами.
Приклад 1