D. Tree 2-Coloring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is decorating a Christmas tree, but he has some strange preferences for what colors to use.

Consider a coloring of the vertices of a tree, using two colors: red and green.

In a coloring, call a connected component of green vertices cool if at most two red vertices are adjacent to that component. For a tree $$$t$$$, let $$$f(t)$$$ be the maximum number of cool components in any coloring of $$$t$$$.

There is a tree $$$t$$$, initially only containing a single vertex, denoted vertex $$$1$$$. Perform $$$N$$$ queries; in the $$$i^{\text{th}}$$$ query, add a leaf vertex by attaching it to vertex $$$a_i$$$. There are two types of test cases, depending on a variable $$$X \in \{0, 1\}$$$:

  • If $$$X = 0$$$, output $$$f(t)$$$ after all queries are completed.
  • If $$$X = 1$$$, output $$$f(t)$$$ after each query.
Input

There are multiple test cases. The input file begins with $$$T$$$ and $$$X$$$ ($$$1 \le T \le 4\cdot 10^4$$$, $$$X \in \{0, 1\}$$$), the number of test cases and the test type respectively.

The first line of each test case contains an integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$).

The second line contains $$$N$$$ integers $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \le i$$$).

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

If $$$X = 0$$$, then for each test case, output $$$f(t)$$$ for the final tree on a single line.

If $$$X = 1$$$, then for each test case, output $$$N$$$ lines, the $$$i^{\text{th}}$$$ line being the value of $$$f(t)$$$ after the $$$i^{\text{th}}$$$ query.

Scoring
  • ($$$25$$$ points) $$$X = 0$$$.
  • ($$$30$$$ points) Each $$$a_i$$$ is chosen uniformly at random from $$$[1, i]$$$.
  • ($$$45$$$ points) No additional constraints.
Examples
Input
2 0
4
1 2 3 3
8
1 2 3 2 3 6 5 7
Output
3
5
Input
2 1
4
1 2 3 3
8
1 2 3 2 3 6 5 7
Output
1
2
2
3
1
2
2
3
4
4
4
5
Note

Sample Explanation 1

For the first test case, we can color vertices $$$1$$$, $$$2$$$, $$$4$$$, and $$$5$$$ green (note that there are $$$N + 1 = 5$$$ vertices since there is already a vertex in the beginning). Then $$$\{1, 2\}$$$, $$$\{4\}$$$, and $$$\{5\}$$$ are cool components.

For the second test case, we can color vertices $$$1$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$8$$$, and $$$9$$$ green. Then $$$\{1\}$$$, $$$\{4\}$$$, $$$\{5, 8\}$$$, $$$\{6\}$$$, and $$$\{9\}$$$ are cool components.

Sample Explanation 2

This sample has the same trees as the first one, but is of type $$$X = 1$$$.