C. Циркуль для дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$n$$$ вершинами, пронумерованными $$$1, 2, \ldots, n$$$. Изначально все вершины окрашены в белый цвет.

Вы можете выполнить следующую двухэтапную операцию:

  1. Выбрать вершину $$$v$$$ ($$$1 \leq v \leq n$$$) и расстояние $$$d$$$ ($$$0 \leq d \leq n-1$$$).
  2. Для всех вершин $$$u$$$ ($$$1 \leq u \leq n$$$) таких, что $$$\text{dist}^\dagger(u,v)=d$$$, покрасить $$$u$$$ в черный цвет.

Постройте последовательность операций для перекрашивания всех вершин дерева в черный цвет, используя минимально возможное количество операций. Можно показать, что это всегда можно сделать, используя не более $$$n$$$ операций.

$$$^\dagger$$$ $$$\text{dist}(x, y)$$$ обозначает количество ребер на (единственном) простом пути между вершинами $$$x$$$ и $$$y$$$ на дереве.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 200$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^3$$$) — количество вершин дерева.

Следующие $$$n - 1$$$ строк каждого набора входных данных описывают ребра дерева. В $$$i$$$-й из этих строк содержатся два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — индексы вершин, соединенных $$$i$$$-м ребром.

Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^3$$$.

Выходные данные

Для каждого набора входных данных сначала выведите одно целое число $$$op$$$ $$$(1 \le op \le n)$$$ — минимальное количество операций, необходимых для перекрашивания всех вершин дерева в черный цвет.

Затем выведите $$$op$$$ строк, каждая из которых содержит $$$2$$$ целых числа. В $$$i$$$-й строке должны содержаться значения $$$v$$$ и $$$d$$$, выбранные для $$$i$$$-й операции ($$$1 \le v \le n$$$, $$$0 \le d \le n - 1$$$).

Необходимо, чтобы в результате $$$op$$$ операций все вершины были покрашены в черный цвет.

Если существует несколько решений, вы можете вывести любое из них.

Пример
Входные данные
4
1
2
1 2
4
1 2
1 3
1 4
7
2 7
3 2
6 4
5 7
1 6
6 7
Выходные данные
1
1 0
2
1 1
2 1
2
1 1
2 1
3
6 1
7 1
2 1
Примечание

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

Во втором наборе входных данных первая операция перекрашивает вершину $$$2$$$ в черный цвет, а вторая операция перекрашивает вершину $$$1$$$ в черный цвет. Можно показать, что за одну операцию невозможно перекрасить обе вершины в черный цвет, поэтому минимальное количество необходимых операций равно $$$2$$$. Другим возможным решением является использование $$$2$$$ операций: $$$(u, r) = (1, 0)$$$ и $$$(u, r) = (2, 0)$$$.

В третьем наборе входных данных первая операция перекрашивает вершины $$$2$$$, $$$3$$$ и $$$4$$$ в черный цвет, а вторая операция перекрашивает вершину $$$1$$$ в черный цвет. Опять же, можно показать, что за $$$1$$$ операцию невозможно перекрасить все вершины в черный цвет, поэтому минимальное количество необходимых операций равно $$$2$$$.

В четвертом наборе входных данных первая операция перекрашивает вершины $$$4$$$, $$$1$$$ и $$$7$$$ в черный цвет, вторая операция перекрашивает вершины $$$2$$$, $$$5$$$ и $$$6$$$ в черный цвет, а третья операция перекрашивает вершины $$$3$$$ и $$$7$$$ в черный цвет. Обратите внимание, что вершину $$$7$$$ разрешено перекрашивать в черный цвет дважды.

Таким образом, каждая вершина была перекрашена хотя бы один раз, причем вершина $$$7$$$ была перекрашена дважды. Можно показать, что невозможно перекрасить все вершины в черный цвет менее чем за $$$3$$$ хода.