Ở một thiên hà xa xôi trong vũ trụ, có $N$ hành tinh với nền văn minh phát triển. Các 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 ở một trong hai trạng thái: đang được sử dụng để đi đến một hành tinh khác, hoặc không được sử dụng. Khi tàu do hành tinh $a$ quản lý đang được sử dụng để đi đến hành tinh $b$, tàu liên tục đi qua lại giữa $a$ và $b$. Khi tàu đi từ $a$ đến $b$, hành khách thông thường có thể lên tàu để đi từ $a$ đến $b$, nhưng khi tàu quay về từ $b$ đến $a$, hành khách thông thường không thể lên tàu vì các vấn đề về nhiên liệu, việc chở hàng và những lý do khác. Khi tàu do hành tinh $a$ quản lý không được sử dụng, tàu chờ tại hành tinh $a$.

Hiện tại, tất cả các tàu đều không được sử dụng. Lịch thay đổi trạng thái của các tàu trong tương lai đã được quyết định. Mỗi thay đổi thuộc một trong hai loại sau.

• Chuyển tàu do hành tinh $a$ quản lý từ trạng thái không được sử dụng sang trạng thái được sử dụng để đi đến hành tinh $b$. Thao tác này chỉ được thực hiện khi hành khách thông thường không thể đi từ $b$ đến $a$ bằng cách đi tàu vũ trụ một số lần.
• Chuyển tàu do hành tinh $a$ quản lý từ trạng thái đang được sử dụng sang trạng thái không được sử dụng.

Hai người đang lên kế hoạch du lịch trong thiên hà này chuẩn bị một số câu hỏi dưới đây để sắp xếp cuộc gặp.

• Tại một thời điểm trong lịch trình, giả sử một người ở hành tinh $a$ và người còn lại ở hành tinh $b$. Họ có thể sử dụng các tàu với tư cách hành khách thông thường để gặp nhau hay không? Nếu có, họ nên gặp nhau ở hành tinh nào để số lần sử dụng tàu là ít nhất? Nói cách khác, có tồn tại hành tinh $c$ mà hành khách thông thường có thể đi tàu một số lần để đến đó từ cả $a$ lẫn $b$ hay không? Nếu có, hành tinh $c$ nào làm nhỏ nhất tổng số lần sử dụng tàu để đi từ $a$ đến $c$ và từ $b$ đến $c$?

Là một lập trình viên xuất sắc, bạn được yêu cầu tìm câu trả lời cho tất cả các câu hỏi của hai người.

Nhiệm vụ

Hãy viết chương trình trả lời các câu hỏi khi được cung cấp lịch thay đổi trạng thái của các tàu và các câu hỏi theo thứ tự thời gian.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên $N,Q$, cách nhau bởi dấu cách, cho biết số hành tinh là $N$ và tổng số thay đổi trạng thái cùng số câu hỏi là $Q$.
• $Q$ dòng tiếp theo mô tả các thay đổi trạng thái và câu hỏi theo thứ tự thời gian. Dòng thứ $i$ trong số đó $(1\le i\le Q)$ chứa hai hoặc ba số nguyên cách nhau bởi dấu cách. Gọi số nguyên đầu tiên là $T_i$, dòng đó thuộc một trong các trường hợp dưới đây.

(i) Khi $T_i=1$

Dòng này chứa các số nguyên $T_i,A_i,B_i$ và biểu diễn thay đổi: chuyển tàu do hành tinh $A_i$ quản lý sang trạng thái được sử dụng để đi đến hành tinh $B_i$.

Đảm bảo rằng $1\le A_i\le N,1\le B_i\le N,A_i\ne B_i$; tại thời điểm này tàu do hành tinh $A_i$ quản lý không được sử dụng; và hành khách thông thường không thể đi từ $B_i$ đến $A_i$ bằng cách đi tàu một số lần.

(ii) Khi $T_i=2$

Dòng này chứa các số nguyên $T_i,A_i$ và biểu diễn thay đổi: chuyển tàu do hành tinh $A_i$ quản lý sang trạng thái không được sử dụng.

Đảm bảo rằng $1\le A_i\le N$ và tại thời điểm này tàu do hành tinh $A_i$ quản lý đang được sử dụng.

(iii) Khi $T_i=3$

Dòng này chứa các số nguyên $T_i,A_i,B_i$ và biểu diễn câu hỏi: tại thời điểm này, nếu một người ở hành tinh $A_i$ và người còn lại ở hành tinh $B_i$, họ có thể sử dụng tàu với tư cách hành khách thông thường để gặp nhau hay không? Nếu có, họ nên gặp nhau ở hành tinh nào để số lần sử dụng tàu là ít nhất?

Đảm bảo rằng $1\le A_i\le N,1\le B_i\le N,A_i\ne B_i$.

Dữ liệu ra

Với mỗi câu hỏi, in ra đầu ra chuẩn, theo thứ tự, mỗi câu trả lời trên một dòng:

• Nếu có thể gặp nhau, in số hiệu hành tinh gặp nhau giúp số lần sử dụng tàu là ít nhất.
• Nếu không thể gặp nhau, in số nguyên $-1$.

Giới hạn

Mọi dữ liệu vào thỏa mãn các điều kiện sau.

• $2\le N\le 1\,000\,000$.
• $1\le Q\le 1\,000\,000$.

Nhiệm vụ con

Nhiệm vụ con 1 [10 điểm]

Thỏa mãn các điều kiện sau.

• $N\le 5\,000$.
• $Q\le 5\,000$.

Nhiệm vụ con 2 [30 điểm]

• Thỏa mãn $T_i\ne 2$ $(1\le i\le Q)$.

Nhiệm vụ con 3 [60 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

-1
4

Ghi chú

Trong ví dụ này, các thay đổi trạng thái và câu hỏi diễn ra theo thứ tự sau.

• Tàu do hành tinh $2$ quản lý chuyển sang trạng thái được sử dụng để đi đến hành tinh $4$.
• Tại thời điểm này, nếu hai người ở hành tinh $2$ và $6$, họ không thể gặp nhau, nên in $-1$.
• Tàu do hành tinh $4$ quản lý chuyển sang trạng thái được sử dụng để đi đến hành tinh $3$.
• Tàu do hành tinh $6$ quản lý chuyển sang trạng thái được sử dụng để đi đến hành tinh $4$.
• Tại thời điểm này, nếu hai người ở hành tinh $2$ và $6$, họ có thể gặp nhau ở hành tinh $3$ hoặc $4$. Để số lần sử dụng tàu là ít nhất, họ nên gặp nhau ở hành tinh $4$, nên in $4$.

Dữ liệu vào 2

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

Dữ liệu ra 2

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