Chuồng Trại Mới

Có $Q$ truy vấn được thực hiện theo thứ tự. Mỗi truy vấn thuộc một trong hai loại:

• B p: Thêm một đỉnh mới vào đồ thị. Nếu $p\ne -1$, nối đỉnh mới này với đỉnh $p$ bằng một cạnh vô hướng. Ngược lại ($p=-1$), đỉnh mới không kết nối với đỉnh nào. Các đỉnh được đánh số từ $1$ theo thứ tự thêm vào.
• Q k: Truy vấn khoảng cách lớn nhất từ đỉnh $k$ đến bất kỳ đỉnh nào đã được thêm vào và có thể đến được từ $k$.

Đồ thị luôn là một rừng (tập hợp các cây không kết nối với nhau). Với mỗi truy vấn loại Q, in ra khoảng cách lớn nhất tương ứng.

Dữ liệu vào

• Dòng đầu tiên: số nguyên $Q$.
• $Q$ dòng tiếp theo, mỗi dòng là một truy vấn:
  • B p — thêm đỉnh mới, kết nối với đỉnh $p$ (hoặc $p=-1$ nếu không kết nối).
  • Q k — truy vấn khoảng cách xa nhất từ đỉnh $k$.

Dữ liệu ra

Với mỗi truy vấn loại Q, in ra một số nguyên trên một dòng — khoảng cách lớn nhất từ đỉnh $k$ đến bất kỳ đỉnh nào có thể đến được.

Ràng buộc

• $1\le Q\le {10}^5$
• Với truy vấn B p: $p=-1$ hoặc $1\le p\le$ (số đỉnh hiện tại)
• Với truy vấn Q k: $1\le k\le$ (số đỉnh hiện tại)
• Đồ thị luôn là một rừng (không có chu trình)

Ví dụ

Ghi chú

• Một đỉnh đứng độc lập (không kết nối đỉnh nào) có khoảng cách xa nhất là $0$.
• Truy vấn Q k chỉ xét các đỉnh đã được thêm vào tính đến thời điểm truy vấn.