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

Иллюстрация первых двух тестовых наборов из примера. Обратите внимание, что во втором случае второй импульс имеет только одну общую станцию $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