D2. Раскраска дерева (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Дано корневое дерево$$$^{\text{∗}}$$$, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, где корень имеет индекс $$$1$$$, а каждая вершина изначально белая. Обозначим расстояние от корня до $$$i$$$-й вершины как $$$d_i$$$. Вы можете выполнять следующую операцию любое число раз:

  1. Выберите подмножество белых вершин $$$S$$$ так, чтобы никакие две вершины в $$$S$$$ не были соединены ребром и не имели одинаковое расстояние до вершины $$$1$$$. Формально, $$$S$$$ должно удовлетворять условиям, что для всех $$$x,y\in S$$$ и $$$x\neq y$$$, $$$d_x\neq d_y$$$, и между $$$x$$$ и $$$y$$$ нет рёбер.
  2. Покрасьте вершины в $$$S$$$ в чёрный цвет.
Ваша задача — найти минимальное количество операций, необходимых для покраски всего дерева в чёрный цвет, и найти способ покраски дерева таким количеством операций.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов. Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем.

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

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

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

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

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

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

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

Для каждого набора входных данных:

  • Выведите количество операций $$$k$$$ в первой строке ($$$1 \leq k \leq n$$$).
  • Затем выведите $$$k$$$ строк. Каждая строка должна начинаться с целого числа $$$m$$$, представляющего размер множества операции ($$$0 \leq m \leq n$$$). После этого должно следовать $$$m$$$ чисел $$$u_1,u_2,\ldots,u_m$$$ ($$$1 \leq u_i \leq n$$$), представляющих $$$m$$$ вершин, которые вы красите в чёрный цвет в этой операции.

Вы должны гарантировать, что:

  • Каждая выполненная вами операция является допустимой.
  • Вы не красите одну и ту же вершину дважды (в одной и той же операции или в разных операциях).
  • После выполнения всех операций все вершины покрашены в чёрный цвет.
  • Количество выполненных вами операций равно $$$x$$$, где $$$x$$$ — минимально возможное количество операций среди всех возможных решений.

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

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

В первом наборе входных данных, $$$d_1=1$$$ и $$$d_2=d_3=d_4=d_5=2$$$. Можно показать, что необходимо выполнить как минимум $$$5$$$ операций, потому что нет двух вершин, которые можно было бы обработать одновременно.

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