Background

This is a non-traditional problem.

Description

As is well known, binary can represent everything in computer science. Therefore, the THU Computing Association has decided to plant some trees on the campus network of the "World's First" University to improve the environment.

However, although the servers are not made of potatoes, the campus network has limited space because more resources must be used to compete with the "City's First" University next door. Storing a tree in a format like JPG or using traditional tree storage methods would consume memory on the order of KB, which is a significant overhead. As a responsible problem setter, the author naturally wants to minimize memory usage.

After repeated discussions, the THU Computing Association decided to use the most primitive binary method to store trees. This way, when visitors see these binary strings, they only need to mentally reconstruct them into vibrant, living trees according to the rules.

The problem is almost solved—the only issue is that the rules seem difficult to design.

Specifically, the THU Computing Association gives a member, Alice, a rooted tree $T$ with $n$ nodes ($n \le 70$). She needs to convert this tree into a binary string $M$ of length $128$ and inform a visitor, Bob, of $n$ and $M$. After receiving $n$ and $M$ (which is all the information Bob has), Bob needs to recover a rooted tree isomorphic to $T$. We say two trees are isomorphic if and only if they are identical in the sense of unlabeled nodes while considering the order of children.

Your task is to implement the encoding and decoding functions for Alice and Bob, respectively.

Implementation Details

You do not need to, and should not, implement the main function. You only need to implement the following two functions:

unsigned __int128 encoder(int n, const int *p);

void decoder(int n, unsigned __int128 M, int *p);

The encoder function is the encoding function. It accepts the number of nodes $n$ and an array $p$ describing the tree, and returns a 128-bit binary string (stored as an unsigned __int128).

The decoder function is the decoding function. It accepts the number of nodes $n$ and the 128-bit binary string $M$ returned by the encoder function. This function can modify the array $p$ to represent a tree.

In both functions, the tree is stored in the following format: nodes are numbered $1, 2, \dots, n$, where the root is node $1$; $p[i]$ represents the parent of node $i$, with $p[1] = 0$.

To reflect the order of children, it is stipulated that children are ordered by their node indices in ascending order.

Note: Node indices are only for the convenience of transmission; during testing, isomorphic trees are considered identical.

Additionally, you may define other variables or functions as needed. However, values modified in global variables during the encoder phase will not be available during the decoder phase.

Each test case contains $m$ sets of data, and you must pass all of them to receive points for that test case.

Global variables can share values between multiple encoder calls and between multiple decoder calls. You can utilize this property to implement your program reasonably.

Your encoder function can only access the $1 \sim n$ positions of array $p$ and cannot modify them. The decoder function can only access or modify the $1 \sim n$ positions of array $p$.

How to Test Your Program

Three files have been provided locally: grader.cpp, encoder.cpp, and decoder.cpp.

You should name your program planttree.cpp, which contains the encoder and decoder functions you wrote.

Place these 4 files in the same folder and compile/run grader.cpp directly.

The interaction library takes input in the following format:

• The first line contains a positive integer $m$, representing the number of data sets.
• The following $m$ sets of data are provided sequentially. For each set:
  • The first line contains a positive integer $n$, representing the size of the tree.
  • The second line contains $n$ space-separated integers, representing the $p$ array of the tree.

Please ensure the input format strictly follows these requirements, otherwise the interaction library may behave unexpectedly.

The interaction library will output information regarding whether your program is correct.

Note: The interaction library creates and uses a file named planttree.tmp during execution.

Examples

Input 1

1
4
0 1 1 1

Output 1

```

#### Note

This test case contains only one tree with four nodes, where all three leaf nodes have the root as their parent.

The following is an implementation that is **not guaranteed to be correct** but can pass this example. You can refer to this implementation to familiarize yourself with how to use the interaction library.

```c++
unsigned __int128 encoder(int n, const int *p)
{
    return 0;
}

void decoder(int n, unsigned __int128 M, int *p)
{
    p[1] = 0;
    p[2] = p[3] = p[4] = 1;
}

Subtasks

This problem has 5 subtasks:

• Subtask 1 (20 points): Special constraint: $n \le 65$, $m \le 3000$.
• Subtask 2 (15 points): Special constraint: $m \le 3000$.
• Subtask 3 (15 points): Special constraint: The depth of the tree does not exceed $10$, where the root (node $1$) has a depth of $1$.
• Subtask 4 (20 points): Special constraint: Each node in the tree has at most $2$ children.
• Subtask 5 (30 points): No special constraints.

For all test cases, it is guaranteed that $n \le 70$ and $m \le 10^5$.

Note

The time limit for this problem is 2s, and the memory limit is 512MB. It is guaranteed that for any valid data and calls within the limits, the interaction library will not take more than 0.5s of time and 64MB of memory, meaning you have at least 1.5s and 448MB available.

The necessary header files for the interaction library are already provided; you may include any additional headers you need.

Note that the interaction library uses using namespace std, so be careful with potential variable name conflicts.

To reflect the actual evaluation environment, the interaction library used for final grading is not identical to the one provided.

Your program must not perform any input, output, or file operations.

Attempting to access input/output files, attacking the evaluation system, or attacking the evaluation library is considered cheating, and any scores obtained will be invalid.

QOJ Evaluation

During QOJ evaluation, the encoder and decoder programs will run in two separate processes to prevent potential cheating.