Піггі (який у вільний час керує Комісією з протоколів міжзоряного зв'язку) зіткнувся з делікатною апаратною проблемою. Новітня комунікаційна мережа, що складається з $n$ ретрансляційних станцій, з'єднаних $(n - 1)$ оптоволоконними лініями у вигляді дерева, нарешті готова до розгортання. Однак вмикати систему потрібно з надзвичайною обережністю.
Процес активації полягає в запуску лазерних імпульсів уздовж певних шляхів. Шлях визначається як єдиний простий маршрут між двома станціями. Через катастрофічний ризик «квантової інтерференції зворотного потоку» — явища, яке не дає спати вночі юристам комісії, — необхідно суворо дотримуватися такого протоколу:
- Шляхи передачі повинні встановлюватися один за одним.
- Щоб запобігти стрибкам потужності, кожен новостворений шлях може мати не більше однієї спільної станції з множиною станцій, уже активованих будь-якими попередніми шляхами.
Формально, нехай $S$ — множина наразі активованих станцій. Для будь-якого нового шляху $P$, що складається з множини станцій $V(P)$, має виконуватися умова $|V(P) \cap S| \le 1$. Щойно вздовж шляху успішно випущено імпульс, усі станції на цьому шляху вважаються частиною активованої множини $S$.
Ваша місія, якщо ви вирішите її прийняти, полягає в тому, щоб визначити мінімальну кількість лазерних імпульсів, необхідних для активації кожної станції в усій мережі, і надати одну таку послідовність шляхів, щоб задовольнити юридичний відділ.

Ілюстрація перших двох тестових випадків прикладу. Зауважте, що у випадку 2 другий імпульс має лише одну спільну станцію $2$ з першим, що задовольняє правило неінтерференції.
Вхідні дані
Є декілька наборів вхідних даних. Перший рядок вхідних даних містить ціле число $T$ ($1 \le T \le 10^4$), що вказує на кількість наборів вхідних даних. Для кожного набору:
Перший рядок містить ціле число $n$ ($2 \le n \le 3 \times 10^5$) — кількість станцій у мережі.
У наступних $(n - 1)$ рядках $i$-й рядок містить два цілі числа $u_i$ та $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), які описують двонаправлену оптоволоконну лінію між станцією $u_i$ та станцією $v_i$.
Гарантується, що лінії утворюють дерево і що сума $n$ за всіма наборами вхідних даних не перевищує $3 \times 10^5$.
Вихідні дані
Для кожного набору вхідних даних у першому рядку виведіть мінімальну кількість шляхів $k$. Після цього виведіть $k$ рядків, кожен з яких містить два цілі числа $a_i$ та $b_i$, що представляють кінці $i$-го шляху в послідовності. Зауважте, що $a_i$ може дорівнювати $b_i$, якщо шлях складається з однієї станції.
Якщо існує декілька оптимальних послідовностей, буде прийнято будь-яку, що суворо дотримується протоколу неінтерференції.
Приклад
Вхідні дані
3 3 1 2 2 3 5 1 2 2 3 2 4 2 5 7 1 2 1 3 2 4 2 5 3 6 3 7
Вихідні дані
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5