[Solution] Vertical Paths solution codeforces

Vertical Paths solution codeforces – You are given a rooted tree consisting of 𝑛n vertices. Vertices are numbered from 11 to 𝑛n. Any vertex can be the root of a tree.

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

[Solution] Vertical Paths solution codeforces

The tree is specified by an array of parents 𝑝p containing 𝑛n numbers: 𝑝𝑖pi 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 55 to 33 (the root), the next vertex would be 11, so the parent of 55 is 11.

The root has no parent, so for it, the value of 𝑝𝑖pi is 𝑖i (the root is the only vertex for which 𝑝𝑖=𝑖pi=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);
  • amount of paths is minimal.

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

  1. 3153→1→5 (path of 33 vertices),
  2. 44 (path of 11 vertices).
  3. 22 (path of 11 vertices).

Vertical Paths solution codeforcesExample of splitting a root tree into three paths for 𝑛=5n=5, the root of the tree — node 33.

[Solution] Vertical Paths solution codeforces

The first line of input data contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases in the test.

Each test case consists of two lines.

The first of them contains an integer 𝑛n (1𝑛21051≤n≤2⋅105). It is the number of vertices in the tree.

The second line contains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤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 21052⋅105.

Output

For each test case on the first line, output an integer 𝑚m — the minimum amount 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.

Example
input

Copy
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

[Solution] Vertical Paths solution codeforces

output

Copy
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

 

For Solution

Click here

Leave a Comment