IOI có \(N\) thành phố, ban đầu chưa có đường. Trong năm \(i\) có kế hoạch cải thiện giao thông giữa \(A_i\) và \(B_i\); \(T_i=1\) nghĩa là kế hoạch được thực hiện trong năm ấy, còn \(T_i=2\) nghĩa là bị hủy.

Khi một kế hoạch được thực hiện:

• Nếu hai thành phố chưa liên thông bởi các đường đã xây, xây một đường hai chiều chưa trải nhựa nối trực tiếp chúng.
• Nếu đã liên thông, xét mọi đường đi dùng ít cạnh nhất giữa chúng và trải nhựa mọi cạnh chưa trải thuộc ít nhất một đường đi ngắn nhất như vậy. Đường đã trải không được trải lại.

Với từng kế hoạch bị hủy, hãy xét trạng thái lịch sử tại đúng thời điểm ấy và giả sử chỉ riêng kế hoạch đó được thực hiện thêm. In số đường sẽ được trải nhựa; nếu nó sẽ xây đường mới thì in -1. Giả định này không làm thay đổi trạng thái cho những năm sau.

Dữ liệu vào

Dòng đầu chứa \(N,Q\). Mỗi trong \(Q\) dòng sau chứa \(T_i,A_i,B_i\).

Dữ liệu ra

Với mỗi kế hoạch có \(T_i=2\), theo thứ tự thời gian, in đáp án trên một dòng.

Ràng buộc

Phân nhóm

• Nhóm 1 (10 điểm): \(N\le1000\), \(Q\le3000\).
• Nhóm 2 (25 điểm): tồn tại \(1\le P\le Q-1\) sao cho \(T_i=1\) với \(i\le P\) và \(T_i=2\) với \(i>P\).
• Nhóm 3 (25 điểm): với mọi kế hoạch được thực hiện, ngay trước khi thực hiện, hai đầu hoặc chưa liên thông, hoặc có một đường đi giữa chúng dùng không quá 200 đường.
• Nhóm 4 (25 điểm): có không quá 200 chỉ số \(i\) với \(T_i=2\).
• Nhóm 5 (15 điểm): không có ràng buộc bổ sung.

Ví dụ

3 7
1 1 2
2 2 1
2 2 3
1 2 1
2 1 2
1 2 3
2 1 3

1
-1
0
1

6 8
1 1 3
1 6 1
1 2 5
2 3 6
1 3 6
1 4 1
2 4 3
2 2 5

2
1
1

7 11
1 5 1
1 6 2
1 1 3
1 3 5
1 5 7
1 4 5
1 4 1
2 1 3
2 3 7
2 4 3
2 5 6

0
1
0
-1