C. Tree Folding
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After giving a super kind shout out to LIT and the Tetris game night during the Berkeley CALICO Fall 2022 contest, Spiralsim forgot to mention that he himself is ranked 65 in the entire US on TETR.IO! Engorged by envy of Spiralsim's greatness, CodeTiger machinates a devilish plan  — proposing another game night for LIT to stop Spiralsim from winning. He conspired with Berkeley's long-time rival, the Stanford tree mascot, and created a brand new game called tree folding. Inspired by the popular game (2048), CodeTiger recreates it on a tree.

A tree is an undirected unweighted connected graph with $$$n$$$ vertices and $$$n-1$$$ edges.

Consider a Stanford tree with $$$n$$$ vertices. For all $$$1 \le i \le n$$$, the $$$i$$$-th vertex has a number written on it, denoted $$$a_i$$$. Initially, all $$$a_i$$$ are $$$0$$$. You are allowed to perform the following fold operation:

  • Choose an edge $$$(u,v)$$$ such that $$$a_u = a_v$$$. Delete this edge, and combine $$$u$$$ and $$$v$$$ into a single new vertex $$$x$$$, with $$$a_x = a_u + 1$$$. All vertices that were connected by an edge to either $$$u$$$ or $$$v$$$ are now connected to $$$x$$$.

Informally, you can think of it like playing 2048 on a tree.

A tree is called good if it is possible to perform this operation repeatedly and end up with a single node. For example, a line graph on $$$4$$$ vertices is good because you can perform these operations:

Now, you are given a tree which initially consists of a single node, and $$$q$$$ queries. In the $$$i$$$-th query ($$$1 \le i \le q$$$), you are given an integer $$$x_i \le i$$$, meaning you should create a new node labeled $$$i+1$$$, and connect it with an undirected edge to node $$$x_i$$$. After each update, determine if the resulting tree is good.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 3 \cdot 10^5$$$).

The first line of each test contains $$$q$$$, the number of queries ($$$1 \le q \le 3 \cdot 10^5$$$).

The second line contains $$$q$$$ integers $$$x_1, x_2, \ldots, x_q$$$ ($$$1 \le x_i \le i$$$).

It is guaranteed the sum of $$$q$$$ over all tests does not exceed $$$3 \cdot 10^5$$$.

Output

For each query, output either YES or NO.

Scoring
  • In tests worth $$$30$$$ points, it is guaranteed that the sum of $$$q$$$ over all tests does not exceed $$$300$$$.
  • In tests worth a further $$$20$$$ points, it is guaranteed that the sum of $$$q$$$ over all tests does not exceed $$$5\,000$$$.
Example
Input
4
3
1 2 3
1
1
7
1 1 3 2 2 1 5
3
1 1 1
Output
YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
YES
YES
NO
NO
Note

In the first test, we build a line graph of size $$$4$$$, like shown in the statement. We can show that line graphs of size $$$2$$$ and $$$4$$$ are good, while those of size $$$3$$$ are not.

Similarly, in the second test, we construct a line of size $$$2$$$.

In the third test, here is a picture of the final graph (which turns out to be good):