You are given a rooted tree consisting of $n$ vertices. Vertices are numbered from $1$ to $n$. Any vertex can be the root of a tree.

A tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root.

The tree is specified by an array of parents $p$ containing $n$ numbers: $p_i$ is a parent of the vertex with the index $i$. The parent of a vertex $u$ is a vertex that is the next vertex on the shortest path from $u$ to the root. For example, on the simple path from $5$ to $3$ (the root), the next vertex would be $1$, so the parent of $5$ is $1$.

The root has no parent, so for it, the value of $p_i$ is $i$ (the root is the only vertex for which $p_i=i$).

Find such a set of paths that:

each vertex belongs to exactly one path, each path can contain one or more vertices;

in each path each next vertex — is a son of the current vertex (that is, paths always lead down — from parent to son);

number of paths is minimal.

For example, if $n=5$ and $p=[3, 1, 3, 3, 1]$, then the tree can be divided into three paths:

$3 \rightarrow 1 \rightarrow 5$ (path of $3$ vertices),

$4$ (path of $1$ vertices).

$2$ (path of $1$ vertices).

Example of splitting a root tree into three paths for $n=5$, the root of the tree — node $3$.


-----Input-----

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

Each test case consists of two lines.

The first of them contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$). It is the number of vertices in the tree.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). It is guaranteed that the $p$ array encodes some rooted tree.

It is guaranteed that the sum of the values $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case on the first line, output an integer $m$ — the minimum number of non-intersecting leading down paths that can cover all vertices of the tree.

Then print $m$ pairs of lines containing path descriptions. In the first of them print the length of the path, in the second — the sequence of vertices specifying that path in the order from top to bottom. You can output the paths in any order.

If there are several answers, output any of them.


-----Examples-----

Input
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
Output
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


-----Note-----

None

Difficulty: EASY
Tags: Tree algorithms

Graph algorithms

Implementation

Starter code:

Solutions:
cases = int(input())
for _ in range(cases):
	n = int(input())
	parents = list(map(int, input().split()))
	if len(parents) == 1:
		print('1\n1\n1')
		continue
	leaves = set((i + 1 for i in range(n))) - set(parents)
	print(len(leaves))
	visited = set()
	for leaf in leaves:
		cur = leaf
		path = [leaf]
		while parents[cur - 1] != cur:
			cur = parents[cur - 1]
			if cur in visited:
				break
			visited.add(cur)
			path.append(cur)
		print(len(path))
		print(' '.join(map(str, reversed(path))))


for g in range(int(input())):
	n = int(input())
	p = [int(i) - 1 for i in input().split()]
	(s, v, a) = (set(p), [1] * n, [])
	for i in range(n):
		if i in s and n > 1:
			continue
		t = []
		while v[i]:
			t += [i + 1]
			v[i] = 0
			i = p[i]
		a += [t[::-1]]
	print(len(a))
	for v in a:
		print(len(v))
		print(*v)


for x in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	used = [False] * n
	g = [[] for i in range(n)]
	for i in range(n):
		if p[i] - 1 != i:
			g[p[i] - 1].append(i)
	c = 0
	s = ''
	for i in range(n):
		if not g[i]:
			c += 1
			ans = []
			l = 0
			while p[i] - 1 != i and (not used[i]):
				used[i] = True
				l += 1
				ans.append(i + 1)
				i = p[i] - 1
			if p[i] - 1 == i and (not used[i]):
				used[i] = True
				ans.append(i + 1)
				l += 1
			s += str(l) + '\n' + ' '.join(map(str, ans[::-1])) + '\n'
	print(c)
	print(s[:len(s) - 1])


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	parents = list(map(int, input().split()))
	if n == 1:
		print(1)
		print(1)
		print(1)
		continue
	leaves = []
	graph = defaultdict(int)
	for i in range(n):
		graph[parents[i]] += 1
	for i in range(1, n + 1):
		if graph[i] == 0:
			leaves.append(i)
	ans = len(leaves)
	ansArray = []
	for leaf in leaves:
		node = leaf
		temp = [node]
		graph[node] = -1
		while parents[node - 1] != node and graph[parents[node - 1]] != -1:
			temp.append(parents[node - 1])
			node = parents[node - 1]
			graph[node] = -1
		ansArray.append(temp[::-1])
	print(ans)
	for i in range(len(ansArray)):
		print(len(ansArray[i]))
		print(*ansArray[i])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	p = [int(i) for i in input().split(' ')]
	if n == 1:
		print('1\n1\n1\n')
		continue
	parents = set(p)
	all_nodes = set(list(range(1, n + 1)))
	leaves = all_nodes - parents
	col = [0 for i in range(n)]
	print(len(leaves))
	for leaf in leaves:
		rpath = [leaf]
		node = leaf
		col[node - 1] = 1
		while col[p[node - 1] - 1] == 0:
			node = p[node - 1]
			col[node - 1] = 1
			rpath.append(node)
		print(len(rpath))
		for i in reversed(rpath):
			print(i, end=' ')
		print('')
	print('')


for _ in range(int(input())):
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	leaves = set(range(n)) - set(p)
	if not leaves:
		print(1)
		print(1)
		print(1)
		continue
	visited = [False] * n
	paths = []
	for i in leaves:
		path = []
		while not visited[i]:
			path.append(i)
			visited[i] = True
			i = p[i]
		paths.append(path)
	print(len(paths))
	for path in paths:
		print(len(path))
		print(' '.join((str(x + 1) for x in reversed(path))))


import math
for i in range(int(input())):
	n = int(input())
	parents = list(map(int, input().split()))
	if n == 1:
		print(1, 1, 1, sep='\n')
		print()
		continue
	childs = [0] * n
	for j in range(n):
		parents[j] -= 1
		childs[parents[j]] = -1
	npaths = 0
	nPathArray = []
	for k in range(n):
		if childs[k] == 0:
			npaths += 1
			newpath = [k]
			childs[k] = npaths
			p = parents[k]
			while childs[p] == -1:
				newpath.append(p)
				childs[p] = npaths
				p = parents[p]
			nPathArray.append(newpath)
	print(len(nPathArray))
	for l in nPathArray:
		print(len(l))
		for m in range(len(l) - 1, -1, -1):
			print(l[m] + 1, end=' ')
		print()
	print()


cnt = int(input())
i = 1
while i <= cnt:
	n = int(input())
	p = input().split()
	if n == 1:
		print(1)
		print(1)
		print(1)
		i += 1
		continue
	mark = [0] * (n + 1)
	for j in range(len(p)):
		p[j] = int(p[j])
		mark[p[j]] = 1
	ans = []
	for node in range(1, n + 1):
		if mark[node] == 0:
			path = []
			now = node
			path.append(now)
			while mark[p[now - 1]] == 1:
				path.append(p[now - 1])
				mark[p[now - 1]] = 2
				now = p[now - 1]
			ans.append(path)
	print(len(ans))
	for a in ans:
		print(len(a))
		for k in reversed(range(len(a))):
			print(a[k], end=' ')
		print('')
	i += 1


N = int(input())
for i in range(N):
	n = int(input())
	ll = list(map(int, input().split()))
	for i in range(n):
		if ll[i] == i + 1:
			root = i + 1
	v = dict()
	for i in range(n):
		if i + 1 != root:
			if ll[i] not in v.keys():
				v[ll[i]] = list()
			v[ll[i]].append(i + 1)
	lvs = [False for i in range(n + 1)]
	lvs[0] = True
	cnt = 0
	for i in ll:
		lvs[i] = True
	for i in lvs:
		if not i:
			cnt += 1
	if n == 1:
		cnt = 1
	print(cnt)
	if n == 1:
		print(1)
		print(ll[0])
	st = [False for i in range(n + 1)]
	for i in range(1, len(lvs)):
		if not lvs[i]:
			cur = i
			tmp = []
			while not st[cur]:
				tmp.append(cur)
				st[cur] = True
				cur = ll[cur - 1]
			print(len(tmp))
			for i in range(len(tmp) - 1, -1, -1):
				print(tmp[i], end=' ')
			print()
	print()