DSU Có Mốc Khôi Phục

Ban đầu có $n$ đỉnh, mỗi đỉnh là một thành phần liên thông riêng. Xử lý $q$ lệnh:

• $union$ $u$ $v$: hợp thành phần chứa $u$ với thành phần chứa $v$ nếu chúng khác nhau, rồi in số thành phần hiện tại.
• persist: đặt một mốc lưu trạng thái hiện tại. Các mốc được quản lý theo ngăn xếp.
• rollback: khôi phục trạng thái tại mốc gần nhất, xóa mốc đó, rồi in số thành phần hiện tại.

Một lệnh $union$ giữa hai đỉnh vốn đã cùng thành phần vẫn là một lệnh hợp lệ và không làm đổi số thành phần.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Mỗi trong $q$ dòng tiếp theo mô tả một lệnh theo một trong ba dạng trên.

Output

• Sau mỗi lệnh $union$ và rollback, in số thành phần liên thông hiện tại trên một dòng riêng. Lệnh persist không tạo đầu ra.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le u,v\le n$.
• Mỗi lệnh rollback luôn có ít nhất một mốc chưa được dùng.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 8
union 1 2
persist
union 2 3
union 1 3
persist
union 4 5
rollback
rollback

4
3
3
2
3
4