A. Assembling Strings from a Trie
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A trie (prefix tree) is a tree-like data structure in which edges are labeled with characters. From any node, all outgoing edges have distinct labels, and the sequence of labels on the path from the root to a node represents a string.

Take the picture below as an example. The path $$$1\rightarrow4\rightarrow8\rightarrow12$$$ represents the string "caa".

In this problem, the alphabet consists of all positive integers, rather than a fixed set of characters.

There are $$$n$$$ non-empty strings $$$S_1, S_2, \dots, S_n$$$ that form a trie $$$T$$$ with $$$m$$$ nodes. Node $$$1$$$ is the root, while the indices of the remaining nodes have been arbitrarily permuted.

Given the structure of the trie, your task is to reconstruct the original strings.

  • If multiple valid reconstructions exist, output the one with the minimum $$$n$$$.
  • If there are still multiple valid solutions, output the lexicographically smallest sequence $$$[S_1, S_2, \dots, S_n]$$$.

The lexicographic order of string sequences is defined as follows: $$$[A_1, A_2, \dots, A_n]$$$ is smaller than $$$[B_1, B_2, \dots, B_n]$$$ if there exists an index $$$k$$$ such that $$$A_i = B_i$$$ for all $$$1 \le i \lt k$$$ and $$$A_k \lt B_k$$$.

The lexicographic order of two integer strings is defined as follows: a string $$$C$$$ is lexicographically smaller than a string $$$D$$$ if and only if either $$$C$$$ is a prefix of $$$D$$$, or there exists an index $$$k ~(1 \le k \le \min(|C|, |D|))$$$ such that $$$C(i) = D(i)$$$ for all $$$1 \le i \lt k$$$ and $$$C(k) \lt D(k)$$$, where $$$C(k)$$$ denotes the $$$k$$$-th element of string $$$C$$$.

Input

The first line contains an integer $$$T~ (1 \le T \le 500)$$$, the number of test cases.

For each test case:

  • One line contains an integer $$$m~ (2 \le m \le 200000)$$$, the number of nodes in the trie.
  • One line contains $$$m-1$$$ integers $$$f_2, f_3, \dots, f_m ~(1 \le f_i \lt i)$$$, where $$$f_i$$$ denotes the parent of node $$$i$$$.

The total number of nodes over all test cases does not exceed $$$2,000,000$$$.

Output

For each test case:

Output one integer $$$n$$$, the number of reconstructed strings.

Then output $$$n$$$ lines. The strings themselves may be extremely long, so only their hash values are required.

The $$$i$$$-th line should contain the hash value of string $$$S_i$$$, defined as $$$$$$ \left( \sum_{j=1}^{|S_i|} 998244353^{|S_i|-j} \cdot S_i(j) \right) \bmod 2^{64}. $$$$$$

Example
Input
4
2
1
3
1 1
4
1 2 1
6
1 2 1 4 5
Output
1
1
2
1
2
2
1
1996488707
2
998244354
1992983577591021572
Note

For the example,

  • testcase 1: The solution is $$$S_1 = [1]$$$.
  • testcase 2: The solution is $$$S_1 = [1],\; S_2 = [2]$$$.
  • testcase 3: The solution is $$$S_1 = [1],\; S_2 = [2, 1]$$$.
  • testcase 4: The solution is $$$S_1 = [1, 1],\; S_2 = [2, 1, 1]$$$.