Busy Beaver はクリスマスツリーの飾り付けをしていますが、使う色について少し変わったこだわりを持っています。
木の頂点を赤と緑の2色で塗り分けることを考えます。
ある塗り方において、緑色の頂点からなる連結成分が、高々2つの赤色の頂点と隣接しているとき、その連結成分を「クール」と呼ぶことにします。木 $t$ に対して、$f(t)$ をその木におけるクールな連結成分の数の最大値とします。
最初は頂点1のみを含む木 $t$ があります。$N$ 回のクエリを行います。$i$ 番目のクエリでは、頂点 $a_i$ に新しい葉頂点を追加します。変数 $X \in \{0, 1\}$ に応じて、以下の2種類のテストケースがあります。
- $X = 0$ の場合、すべてのクエリが完了した後の $f(t)$ を出力してください。
- $X = 1$ の場合、各クエリの後の $f(t)$ を出力してください。
入力
複数のテストケースが含まれます。入力ファイルの先頭には、テストケースの数 $T$ とテストの種類 $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$) が与えられます。
各テストケースの1行目には、整数 $N$ ($1 \le N \le 2 \cdot 10^5$) が与えられます。
2行目には、$N$ 個の整数 $a_1, \dots, a_N$ ($1 \le a_i \le i$) が与えられます。
すべてのテストケースにおける $N$ の総和は $4 \cdot 10^5$ を超えないことが保証されています。
出力
$X = 0$ の場合、各テストケースについて、最終的な木に対する $f(t)$ を1行で出力してください。
$X = 1$ の場合、各テストケースについて $N$ 行出力してください。$i$ 行目には、$i$ 番目のクエリ後の $f(t)$ の値を出力してください。
小課題
- ($25$ 点) $X = 0$。
- ($30$ 点) 各 $a_i$ は $[1, i]$ から一様ランダムに選ばれる。
- ($45$ 点) 追加の制約なし。
入出力例
入力 1
2 0 4 1 2 3 3 8 1 2 3 2 3 6 5 7
出力 1
3 5
入力 2
2 1 4 1 2 3 3 8 1 2 3 2 3 6 5 7
出力 2
1 2 2 3 1 2 2 3 4 4 4 5
注記
入出力例 1 の説明
1つ目のテストケースでは、頂点 $1, 2, 4, 5$ を緑色に塗ることができます（最初から頂点が1つあるため、頂点は合計 $N + 1 = 5$ 個存在することに注意してください）。このとき、$\{1, 2\}$, $\{4\}$, $\{5\}$ がクールな連結成分となります。
2つ目のテストケースでは、頂点 $1, 4, 5, 6, 8, 9$ を緑色に塗ることができます。このとき、$\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$, $\{9\}$ がクールな連結成分となります。
入出力例 2 の説明
このサンプルは1つ目と同じ木を使用していますが、$X = 1$ のタイプです。