Пигги (который в свободное время управляет Комиссией по протоколам межзвездной связи) столкнулся с деликатной аппаратной проблемой. Новейшая коммуникационная сеть, состоящая из $n$ ретрансляционных станций, соединенных $(n - 1)$ оптоволоконными линиями в структуру дерева, наконец готова к развертыванию. Однако система должна быть запущена с особой осторожностью.

Процесс активации включает в себя запуск лазерных импульсов по определенным путям. Путь определяется как единственный простой маршрут между двумя станциями. Из-за катастрофического риска «квантовой интерференции обратного потока» — явления, которое не дает юристам комиссии спать по ночам, — необходимо строго соблюдать следующий протокол:

• Пути передачи должны устанавливаться один за другим.
• Чтобы предотвратить скачки напряжения, каждый вновь установленный путь может иметь не более одной общей станции с множеством станций, уже активированных любым предыдущим путем.

Формально, пусть $S$ — множество уже активированных станций. Для любого нового пути $P$, состоящего из множества станций $V(P)$, должно выполняться условие $|V(P) \cap S| \le 1$. После успешного запуска импульса по пути все станции на этом пути считаются частью активированного множества $S$.

Ваша задача, если вы решите ее принять, — определить минимальное количество лазерных импульсов, необходимых для активации каждой станции во всей сети, и предоставить одну такую последовательность путей, удовлетворяющую требованиям юридического отдела.

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

Если существует несколько оптимальных последовательностей, будет принята любая, которая строго следует протоколу отсутствия интерференции.

Примеры

Примеры 1

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
1 3
2
4 5
1 3
3
7 7
1 6
4 5