To read the problem statement in English, choose the language using the flag on the navigation bar.

Phát có em gái rất siêng năng học hỏi. Tuy nhiên môn lịch sử lúc nào cũng là trở ngại đối với em gái của Phát, do đó Phát sẽ kèm em gái của mình học môn lịch sử. Hôm nay hai bạn sẽ ôn lại về tầm ảnh hưởng của phát triển công nghệ ảnh hưởng thế nào đến các quốc gia trên thế giới.

Như chúng ta đã biết, trên thế giới có ~n~ quốc gia tồn tại và phát triển đọc lập với nhau. Phát sẽ giúp em gái ôn lại một số sự kiện nổi bật sau:

• Đầu tiên là sự ra đời và phát triển của máy bay và đường hàng không. Cho đến nay, máy bay vẫn là phương tiện nhanh chóng và an toàn nhất. Xây dựng sân bay và sử dụng đường hàng không là một bước không thể thiếu đối với một quốc gia có nền công nghệ phát triển. Tại một thời điểm nào đó, sẽ có hai quốc gia ~u~ và ~v~ mở tuyến đường hàng không qua lại với nhau. Sau sự kiện này, mọi người có thể bay từ quốc gia ~u~ sang quốc gia ~v~, và ngược lại.

• Hợp tác quốc tế trong lĩnh vực công nghệ cũng là một hướng phát triển trong lĩnh vực này. Tại một thời điểm nào đó, sẽ có hai quốc gia ~x~ và ~y~ kí hiệp ước hợp tác với nhau trong lĩnh vực công nghệ.

• Sự kiện đáng chú ý nhất trong lịch sử có lẽ là một phát kiến công nghệ. Khi một quốc gia ~k~ có một phát kiến công nghệ, quốc gia này sẽ gửi thư mời các đại sứ, cũng như các kĩ sư của các nước mà quốc gia này đã có hiệp ước trước đó đến quốc gia ~k~ để tham gia hội thảo về công nghệ mới nhất này. Tuy nhiên, hội thảo chỉ diễn ra trong thời gian ngắn, nên các khác mời được mời đến phải sử dụng đường hàng không để đến kịp hội thảo. Máy bay di chuyển rất nhanh, nên các khách mời có thể bay qua một số quốc gia trung gian. Tuy nhiên, nếu quốc gia ~h~ nhận được thư mời từ quốc gia ~k~, nhưng từ quốc gia ~h~ không có tuyến bay nào đến quốc gia ~k~, vậy quốc gia ~h~ sẽ không cử đại diện đến tham dự hội thảo.

Phát đã giảng lại cho em của mình ~q~ sự kiện trên theo trình tự thời gian, nhưng em gái vẫn khó thể nào mà nhớ được các sự kiện này. Để giúp em gái của mình có có ấn tượng tốt hơn về các sự kiện, Phát đố: với mỗi mội thảo, hãy tính xem có bao nhiêu quốc gia có thể cử đại diện đến tham gia được hội thảo này.

Cho biết có ~n~ quốc gia độc lập, ban đầu chưa thiết lập đường bay đến nhau, cũng như chưa hiệp ước nào được kí, và cho biết danh sách ~q~ sự kiện được diễn ra theo trình tự thời gian. Hãy giúp em gái của Phát trả lời câu đố của phát cho từng sự kiện hội thảo.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n \le 2 \cdot 10^5~, ~1 \le q \le 6 \cdot 10^5~), lần lượt là số lượng quốc gia và số sự kiện mà Phát đã giảng cho em gái.

Mỗi dòng trong ~q~ dòng tiếp theo mô tả các sự kiện theo mô tả sau:

• 1 u v  – mô tả sự kiện quốc gia ~u~ và ~v~ (~1 \le u, v \le n~, ~u \ne v~) mở tuyến đường hàng không qua lại với nhau. Dữ liệu đảm bảo trước đó quốc gia ~u~ và ~v~ chưa thiết lập đường hàng không với nhau.

• 2 x y  – mô tả sự kiện quốc gia ~x~ và ~y~ (~1 \le x, y \le n~, ~x \ne y~) kí hiệp ước hợp tác với nhau trong lĩnh vực công nghệ. Dữ liệu đảm bảo trước đó quốc gia ~x~ và ~y~ chưa kí hiệp ước hợp tác với nhau.

• 3 k  – mô tả sự kiện quốc gia ~k~ (~1 \le k \le n~) có phát kiến công nghệ mới và gửi thư mời các quốc gia đã có hiệp ước với quốc gia ~k~ trước đó đến quốc gia ~k~ để tham gia hội thảo về công nghệ. Dữ liệu đảm bảo có ít nhât một sự kiện loại này.

Output

Với mỗi sự kiện hội thảo (tức sự kiện loại 3), hãy in ra số lượng các quốc gia có thể cử đại diện tham gia hội thảo công nghệ.

Scoring

• Subtask 1, tương ứng với ~80~ điểm, có ~n \leq 10^3~ và ~q \leq 3 \cdot 10^3~.

• Subtask 2, tương ứng với ~125~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~205~ điểm.

Sample Input 1

4 8
1 1 3
2 1 4
3 1
1 4 1
2 1 2
3 4
1 2 4
3 1

Sample Output 1

0
1
2

Notes

Sự kiện hội thảo đầu tiên do quốc gia ~1~ tổ chức. Trước đó quốc gia ~1~ và ~4~ đã kí hiệp ước với nhau, nhưng quốc gia ~1~ mới chỉ có đường bay đến quốc gia ~3~, nên lúc đó quốc gia ~4~ không thể cử đại diện đến tham gia hội thảo được.

Sự kiện hội thảo tiếp theo do quốc gia ~4~ tổ chức. Lúc này từ quốc gia ~1~ đã có thể bay trực tiếp đến quốc gia ~4~. Lưu ý, quốc gia ~2~ không có hiệp ước với quốc gia ~4~, mà chỉ có hiệp ước với quốc gia ~1~.

Ở sự kiện hội thảo cuối cùng, quốc gia ~1~ lại tổ chức. Lúc này cả hai quốc gia ~2~ và ~4~ đều có thể cử đại diện đến hội thảo. Từ quốc gia ~4~ có thể bay trực tiếp đến quốc gia ~1~, còn từ quốc gia ~2~ đến cần bay đến quốc gia ~4~, rồi từ quốc gia ~4~ bay đến quốc gia ~1~ để tham gia hội thảo.