Trong một thiên hà xa xôi có \(N\) hành tinh được đánh số từ \(1\) đến \(N\). Mỗi hành tinh quản lý một tàu vũ trụ. Mỗi tàu hoặc đang ngừng hoạt động, hoặc đang phục vụ một tuyến đến một hành tinh khác.

Nếu tàu do hành tinh \(a\) quản lý phục vụ tuyến đến hành tinh \(b\), tàu sẽ liên tục đi qua lại giữa hai hành tinh. Tuy nhiên, hành khách thông thường chỉ được đi từ \(a\) đến \(b\); chuyến trở về từ \(b\) đến \(a\) không chở hành khách. Khi ngừng hoạt động, tàu đỗ tại hành tinh quản lý nó.

Ban đầu, tất cả các tàu đều ngừng hoạt động. Lịch thay đổi trạng thái tàu đã được xác định, với hai loại thay đổi:

• Cho tàu đang ngừng hoạt động của hành tinh \(a\) bắt đầu phục vụ tuyến đến hành tinh \(b\). Thay đổi này chỉ được thực hiện khi hành khách chưa thể đi từ \(b\) đến \(a\) bằng các tuyến đang hoạt động.
• Cho tàu đang hoạt động của hành tinh \(a\) ngừng hoạt động.

Hai người đang lên kế hoạch du lịch muốn trả lời các câu hỏi tại những thời điểm trong lịch trình. Nếu một người ở hành tinh \(a\), người kia ở hành tinh \(b\), liệu họ có thể gặp nhau bằng cách sử dụng các tuyến dành cho hành khách hay không? Nếu có, họ nên gặp nhau ở hành tinh nào để tổng số lượt đi tàu của cả hai nhỏ nhất?

Cụ thể, cần tìm một hành tinh \(c\) mà cả hai đều có thể đến từ vị trí của mình, sao cho tổng số lượt đi tàu từ \(a\) đến \(c\) và từ \(b\) đến \(c\) nhỏ nhất. Một người có thể ở nguyên hành tinh đang đứng và sử dụng \(0\) lượt đi tàu. Mỗi câu hỏi xét các tuyến đang hoạt động tại thời điểm đó.

Yêu cầu

Cho các thay đổi trạng thái và các câu hỏi theo thứ tự thời gian, hãy trả lời tất cả câu hỏi.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,Q\), trong đó \(Q\) là tổng số thay đổi và câu hỏi.
• Mỗi dòng trong \(Q\) dòng tiếp theo mô tả một sự kiện theo thứ tự thời gian, thuộc một trong ba dạng dưới đây. Các số trên cùng dòng được phân cách bằng dấu cách.

Các dạng sự kiện:

• 1 Ai Bi: Cho tàu của hành tinh \(A_i\) bắt đầu phục vụ tuyến đến hành tinh \(B_i\). Bảo đảm \(1 \le A_i,B_i \le N\), \(A_i \ne B_i\), tàu của \(A_i\) hiện đang ngừng hoạt động, và hành khách hiện chưa thể đi từ \(B_i\) đến \(A_i\).
• 2 Ai: Cho tàu của hành tinh \(A_i\) ngừng hoạt động. Bảo đảm \(1 \le A_i \le N\) và tàu này hiện đang hoạt động.
• 3 Ai Bi: Hỏi nơi gặp nhau tối ưu của hai người hiện ở \(A_i\) và \(B_i\). Bảo đảm \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\).

Gọi \(T_i\) là số đầu tiên trên dòng mô tả sự kiện thứ \(i\).

Dữ liệu ra

Với mỗi câu hỏi, theo thứ tự xuất hiện, ghi ra đầu ra chuẩn một dòng:

• Nếu hai người có thể gặp nhau, ghi số hiệu hành tinh gặp nhau làm tổng số lượt đi tàu nhỏ nhất.
• Nếu không thể gặp nhau, ghi -1.

Giới hạn

• \(2 \le N \le 1\,000\,000\).
• \(1 \le Q \le 1\,000\,000\).
• Thời gian: 10 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (10 điểm): \(N \le 5\,000\) và \(Q \le 5\,000\).
• Bài toán con 2 (30 điểm): \(T_i \ne 2\) với mọi \(1 \le i \le Q\); không có sự kiện ngừng hoạt động một tàu.
• Bài toán con 3 (60 điểm): Không có giới hạn bổ sung.

Ví dụ

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

-1
4

Đầu tiên, tuyến \(2 \to 4\) bắt đầu hoạt động. Hai người ở \(2\) và \(6\) chưa thể gặp nhau, nên câu trả lời đầu tiên là \(-1\).

Sau đó, các tuyến \(4 \to 3\) và \(6 \to 4\) bắt đầu hoạt động. Hai người ở \(2\) và \(6\) có thể gặp nhau tại \(3\) hoặc \(4\). Gặp tại \(4\) cần tổng cộng \(2\) lượt đi tàu, ít hơn so với gặp tại \(3\), nên câu trả lời là \(4\).

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6