E. Пересечение диаметров
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин. Диаметром дерева называется простой путь максимальной длины в этом дереве. Длина пути равна числу рёбер в нём. Для заданного дерева длина диаметра является нечётным числом.

Назовем число $$$k$$$ красивым, если в дереве существуют два диаметра (возможно, с совпадающими концами; в том числе это может быть один и тот же диаметр), пересечение которых содержит ровно $$$k$$$ общих ребер.

Найдите все красивые значения $$$k$$$ и выведите их в возрастающем порядке.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных задан в следующем формате:

  • первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — количество вершин дерева;
  • следующие $$$n - 1$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), обозначающие ребро между вершинами $$$u$$$ и $$$v$$$.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$;
  • в каждом наборе входных данных ребра задают дерево с нечетной длиной диаметра.
Выходные данные

Для каждого набора данных сначала выведите одно целое число $$$m$$$ — количество красивых значений $$$k$$$. Затем выведите сами значения $$$k$$$ в возрастающем порядке.

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

Рассмотрим первые три примера из условия:

  • в первом примере пара диаметров $$$(1, 2)$$$ и $$$(1, 2)$$$ дает значение $$$k=1$$$;
  • во втором примере пара диаметров $$$(1, 4)$$$ и $$$(4, 1)$$$ дает значение $$$k=3$$$;
  • в третьем примере пара диаметров $$$(6, 4)$$$ и $$$(3, 5)$$$ дает значение $$$k=1$$$; пара диаметров $$$(6, 4)$$$ и $$$(4, 5)$$$ дает значение $$$k=2$$$; пара диаметров $$$(6, 4)$$$ и $$$(6, 4)$$$ дает значение $$$k=3$$$.