Trong bài toán này, chúng ta cần cài đặt DSU Rollback cơ bản.

Cho ~N~ tập, tập thứ ~i~ hiện tại đang chứa số ~i~.

Chúng ta có ~Q~ truy vấn thuộc một trong ba loại.

• "~union~ ~u~ ~v~" — gộp 2 tập chứa số ~u~ và ~v~, và in ra số tập hiện tại.

• "~persist~" — tạo ra một checkpoint để lúc sau chúng ta có thể quay lại.

• "~rollback~" — đưa các tập về trạng thái ở checkpoint gần nhất, xóa checkpoint đó, và in ra số tập hiện tại.

Input

Dòng đầu tiên chứa số ~N~ ~(N \leq 2 \times 10^5)~ và ~Q~ ~(Q \leq 2 \times 10^5)~ lần lượt là số tập và số truy vấn.

~Q~ dòng tiếp theo bao gồm các truy vấn gồm một trong ba loại (ý nghĩa của từng loại truy vấn như trên):

• ~union~ ~u~ ~v~ ~(1 \le u, v \le N, u < v)~

• ~persist~

• ~rollback~

Output

Với mỗi truy vấn loại ~union~ hoặc ~rollback~, in ra đáp án tương ứng.

Scoring

Sample Input 1

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

Sample Output 1

4
3
2
2
3
2
5
4

Sample Input 2

4 10
persist
union 1 2
union 2 3
persist
union 1 3
persist
union 1 4
rollback
rollback
rollback

Sample Output 2

3
2
2
1
2
2
4

Notes

Giải thích test đề ~1~:

• Đầu tiên, ta đặt checkpoint đầu tiên (nếu lúc sau ta có rollback về checkpoint này, ta sẽ phải xóa đi tất cả những cạnh trước đây)

• Sau đó, ta gộp các tập ~(1, 2)~ và ~(3, 4)~. Khi đó chúng ta còn lại lần lượt ~4~ và ~3~ tập.

• Ta tiếp tục đặt thêm ~1~ checkpoint.

• Ta gộp các tập chứa ~1~ và ~4~. Khi đó ta còn ~2~ tập — ~1~ tập chứa ~{1, 2, 3, 4}~ và tập còn lại chứa ~5~.

• Ta gộp tập chứa ~2~ và ~3~, tuy nhiên do ~2~ và ~3~ thuộc cùng ~1~ tập nên truy vấn này không làm thay đổi số tập.

• Ta rollback, tức quay lại trạng thái trước checkpoint thứ ~2~, và xóa đi checkpoint này. Khi đó ta có ~2~ tập lần lượt là ~{1, 2, 5}~ và ~{3, 4}~

• Ta tiếp tục rollback về lại checkpoint đầu tiên, và xóa đi tất cả các lần gộp từ đầu tới giờ. Do đó ta quay trở về với ~5~ tập.

• Ta gộp ~2~ tập ~{1, 5}~ và khi đó chúng ta có ~4~ tập.