H. Ремонт дорог в Древляндии
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Древляндии $$$n$$$ городов и $$$n-1$$$ двусторонняя дорога. Каждая дорога соединяет пару различных городов. Из любого города можно проехать в любой другой, двигаясь только по дорогам. Города пронумерованы от $$$1$$$ до $$$n$$$. Да, конечно, вы узнали в этом описании неориентированное дерево.

Правительство страны планирует отремонтировать все дороги. Каждая дорога будет отремонтирована некоторой частной компанией. Всего в стране $$$10^6$$$ частных компаний, которые пронумерованы от $$$1$$$ до $$$10^6$$$. Допустимо, что некоторые компании не получат вообще дорог для ремонта, а некоторые будут ремонтировать множество дорог.

Для упрощения контроля за работой частных компаний было введено следующее ограничение: для каждого города посчитаем количество различных компаний, которые чинят дороги, имеющие одним из концов этот город. Это число для каждого города не должно превосходить $$$2$$$. Иными словами, для каждого города должно быть не более двух различных компаний, которые чинят дороги, имеющие отношение к этому городу.

Национальный антикоррупционный комитет Древляндии опасается, что вся (или почти вся) работа достанется одной частной компании. По этой причине комитет требует, чтобы дороги были распределены по компаниям таким образом, чтобы минимизировать величину $$$r$$$. Для каждой компании посчитаем количество назначенных ей дорог, максимум по этим количествам среди всех компаний называется числом $$$r$$$.

Помогите правительству найти такой способ распределить все дороги по компаниям требуемым образом.

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

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее записаны сами наборы входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 3000$$$) — количество городов в Древляндии. Далее в $$$n-1$$$ строке записаны дороги по одному в строке: строка содержит два целых числа $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), обозначающих, что $$$i$$$-я дорога соединяет города $$$x_i$$$ и $$$y_i$$$.

Гарантируется, что сумма всех значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$3000$$$.

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

Выведите ответы для всех $$$t$$$ наборов входных данных в тесте. Каждый набор должен начинаться строкой, которая содержит $$$r$$$ — минимальное возможное количество дорог, назначенных наиболее используемой компании. Далее в следующей строке выведите $$$n-1$$$ число $$$c_1, c_2, \dots, c_{n-1}$$$ ($$$1 \le c_i \le 10^6$$$), где $$$c_i$$$ обозначает номер компании, которой назначен ремонт $$$i$$$-й дороги. Если существует несколько способов назначения, выведите любой из них.

Пример
Входные данные
3
3
1 2
2 3
6
1 2
1 3
1 4
1 5
1 6
7
3 1
1 4
4 6
5 1
2 4
1 7
Выходные данные
1
10 20
3
1 1 1 2 2 
2
11 11 12 13 12 13