Busy Beaver đang trang trí một cây thông Noel, nhưng chú ta có những sở thích kỳ lạ về việc sử dụng màu sắc.

Xét một cách tô màu các đỉnh của một cây bằng hai màu: đỏ và xanh lá cây.

Trong một cách tô màu, một thành phần liên thông gồm các đỉnh màu xanh lá cây được gọi là cool nếu có tối đa hai đỉnh màu đỏ kề với thành phần đó. Với một cây $t$, gọi $f(t)$ là số lượng thành phần cool lớn nhất trong bất kỳ cách tô màu nào của $t$.

Có một cây $t$, ban đầu chỉ chứa một đỉnh duy nhất, ký hiệu là đỉnh $1$. Thực hiện $N$ truy vấn; trong truy vấn thứ $i$, thêm một đỉnh lá bằng cách nối nó vào đỉnh $a_i$. Có hai loại bộ dữ liệu kiểm thử, phụ thuộc vào biến $X \in \{0, 1\}$:

• Nếu $X = 0$, xuất ra $f(t)$ sau khi tất cả các truy vấn đã hoàn tất.
• Nếu $X = 1$, xuất ra $f(t)$ sau mỗi truy vấn.

Dữ liệu vào

Có nhiều bộ dữ liệu kiểm thử. Tệp đầu vào bắt đầu bằng $T$ và $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$), lần lượt là số lượng bộ dữ liệu kiểm thử và loại bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu kiểm thử chứa một số nguyên $N$ ($1 \le N \le 2 \cdot 10^5$).

Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$ ($1 \le a_i \le i$).

Đảm bảo rằng tổng $N$ trên tất cả các bộ dữ liệu kiểm thử không vượt quá $4 \cdot 10^5$.

Dữ liệu ra

Nếu $X = 0$, với mỗi bộ dữ liệu kiểm thử, xuất ra $f(t)$ cho cây cuối cùng trên một dòng.

Nếu $X = 1$, với mỗi bộ dữ liệu kiểm thử, xuất ra $N$ dòng, dòng thứ $i$ là giá trị của $f(t)$ sau truy vấn thứ $i$.

Chấm điểm

• ($25$ điểm) $X = 0$.
• ($30$ điểm) Mỗi $a_i$ được chọn ngẫu nhiên đồng nhất từ $[1, i]$.
• ($45$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

2 0
4
1 2 3 3
8
1 2 3 2 3 6 5 7

Ví dụ 1

3
5

Ví dụ 2

2 1
4
1 2 3 3
8
1 2 3 2 3 6 5 7

Ví dụ 2

1
2
2
3
1
2
2
3
4
4
4
5

Ghi chú

Giải thích ví dụ 1

Đối với bộ dữ liệu kiểm thử đầu tiên, chúng ta có thể tô màu các đỉnh $1$, $2$, $4$ và $5$ bằng màu xanh lá cây (lưu ý rằng có $N + 1 = 5$ đỉnh vì đã có sẵn một đỉnh ngay từ đầu). Khi đó $\{1, 2\}$, $\{4\}$ và $\{5\}$ là các thành phần cool.

Đối với bộ dữ liệu kiểm thử thứ hai, chúng ta có thể tô màu các đỉnh $1$, $4$, $5$, $6$, $8$ và $9$ bằng màu xanh lá cây. Khi đó $\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$ và $\{9\}$ là các thành phần cool.

Giải thích ví dụ 2

Ví dụ này có các cây giống như ví dụ đầu tiên, nhưng thuộc loại $X = 1$.