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

Задано корневое дерево из $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$. Корнем может быть любая из вершин.

Дерево — это связный неориентированный граф без циклов. Корневое дерево — дерево с выделенной вершиной, которую называют корнем.

Дерево задано массивом предков $$$p$$$, содержащим $$$n$$$ целых чисел: $$$p_i$$$ — предок вершины с номером $$$i$$$. Предком вершины $$$u$$$ называется такая вершина, которая является следующей вершиной на кратчайшем пути от $$$u$$$ к корню. Например, на простом пути из $$$5$$$ в $$$3$$$ (корень), следующая вершина будет $$$1$$$, таким образом, предком вершины $$$5$$$ является вершина $$$1$$$.

У корня предка нет, для него в качестве $$$p_i$$$ используется значение $$$i$$$ (таким образом, корень — единственная вершина, для которой $$$p_i=i$$$).

Найдите такой набор путей, что:

  • каждая вершина принадлежит ровно одному пути, каждый путь может содержать одну или более вершину;
  • в каждом пути каждая очередная вершина — это сын текущей вершины (то есть пути всегда ведут вниз — от родителя к сыну);
  • количество путей минимально.

Например, если $$$n=5$$$ и $$$p=[3, 1, 3, 3, 1]$$$, то дерево можно разбить на три пути:

  1. $$$3 \rightarrow 1 \rightarrow 5$$$ (путь из $$$3$$$ вершин),
  2. $$$4$$$ (путь из $$$1$$$ вершины),
  3. $$$2$$$ (путь из $$$1$$$ вершины).
Пример разбиения корневого дерева на три пути для $$$n=5$$$, корень дерева — вершина $$$3$$$.
Входные данные

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

Каждый набор входных данных состоит из двух строк.

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

Во второй записано $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). Гарантируется, что массив $$$p$$$ кодирует некоторое корневое дерево.

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

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

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

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

Если ответов несколько, выведите любой из них.

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

2
2
1 2
2
4 3

1
7
1 2 3 4 5 6 7

1
1
1

3
3
4 1 5
2
2 6
1
3

3
2
2 1
1
3
1
4