After being dumped by two consecutive freshman dance partners who claimed to be busy, Bronya18C decided to intensify their algorithm competition training.
One day, while training, Bronya18C encountered the following problem:
Given a forest of rooted trees, two players, Bronya18C and Bronya19C, take turns making moves, with Bronya18C going first.
At the start of each turn, if the forest is empty, the current player loses the game.
Otherwise, the current player must choose a node $u$, and remove all nodes on the unique simple path from the root $r$ of the connected component containing $u$ to node $u$, as well as all edges incident to these nodes.
After the operation, the root of each newly created connected component is the node in that component that was originally closest to $r$.
Clearly, both Bronya18C and Bronya19C are perfectly rational. You need to determine who will win when both players play optimally.
Since this is an IOI-style contest, to prove that you can truly solve this problem, you must also calculate the SG value of the initial state[^1].
Having been retired for too long, Bronya18C finds that they can no longer write code. Please help them!
Input
The first line contains a positive integer $T$, representing the number of connected components in the forest of rooted trees.
Then, $T$ rooted trees are provided sequentially. Each rooted tree is input in the following format:
The first line contains a positive integer $n$, representing the number of nodes in the rooted tree. The nodes are numbered from $1$ to $n$, and the rooted tree has node $1$ as its root.
If $n \neq 1$, the next line contains $n - 1$ positive integers, where the $i$-th positive integer represents the parent $p_{i + 1}$ of node $i + 1$ in the rooted tree.
Output
Output a single integer representing the SG value of the initial state.
Examples
Input 1
10 1 2 1 3 1 2 4 1 1 2 5 1 2 2 1 6 1 1 3 3 5 7 1 2 1 3 5 6 8 1 1 2 2 3 3 5 9 1 2 3 3 2 3 5 6 10 1 2 3 3 2 3 2 6 1
Output 1
9
Input 2 ~ 5
See the provided files sample2.in, sample3.in, sample4.in, and sample5.in, which satisfy the constraints of subtasks 1, 2, 3, and 4, respectively.
Output 2 ~ 5
See the provided files sample2.ans, sample3.ans, sample4.ans, and sample5.ans.
Constraints
Let $\sum n$ be the total number of nodes in the forest of rooted trees.
For all test cases, $1 \le \sum n \le 2 \times 10^6, 1 \le p_i < i$.
| Subtask ID | $\sum n \le$ | Special Property | Score |
|---|---|---|---|
| 1 | 5000 | None | 10 |
| 2 | $2 \times 10^6$ | $p_i$ is chosen uniformly at random from $[1, i - 1] \cap \mathbb{Z}$ | 10 |
| 3 | $2 \times 10^5$ | None | 30 |
| 4 | $2 \times 10^6$ | 50 |