Nông dân John quản lý một tập hợp \(N\) trang trại (\(1\le N\le 10^5\)), được đánh số thuận tiện từ \(1\ldots N\). Ban đầu, không có con đường nào nối các trang trại với nhau, và mỗi trang trại đều đang tích cực sản xuất sữa.

Do nền kinh tế luôn biến động, Nông dân John cần thay đổi các trang trại của mình theo một chuỗi \(Q\) thao tác cập nhật (\(0\le Q\le 2\cdot 10^5\)). Các thao tác cập nhật có thể thuộc một trong ba dạng:

• (D x) Ngừng hoạt động một trang trại \(x\) đang hoạt động, khiến nó không còn sản xuất sữa.
• (A x y) Thêm một con đường giữa hai trang trại đang hoạt động \(x\) và \(y\).
• (R e) Xóa con đường thứ \(e\) đã được thêm trước đó (\(e=1\) là con đường đầu tiên được thêm).

Một trang trại \(x\) đang tích cực sản xuất sữa, hoặc có thể đi đến một trang trại đang hoạt động khác qua một chuỗi các con đường, được gọi là trang trại “có liên quan”. Với mỗi trang trại \(x\), hãy tính giá trị \(i\) lớn nhất (\(0\le i\le Q\)) sao cho \(x\) có liên quan sau lần cập nhật thứ \(i\).

Dữ liệu vào

Dòng đầu chứa \(N\) và \(Q\). Mỗi dòng trong \(Q\) dòng tiếp theo chứa một cập nhật thuộc một trong các dạng sau:

D x
A x y
R e

Đảm bảo rằng với các cập nhật loại R, \(e\) không vượt quá số con đường đã được thêm cho đến thời điểm đó, và không có hai cập nhật loại R nào có cùng giá trị \(e\).

Dữ liệu ra

In \(N\) dòng, mỗi dòng chứa một số nguyên trong khoảng \(0\ldots Q\).

Phân nhóm

• Các test 2 đến 5 thỏa mãn \(N\le 10^3\), \(Q\le 2\cdot 10^3\).
• Các test 6 đến 20 không có ràng buộc bổ sung.

Ví dụ

5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3

7
8
6
9
9

Nguồn

USACO 2022 January Contest, Gold — Farm Updates: https://usaco.org/index.php?page=viewproblem2&cpid=1186

Tác giả: Benjamin Qi.