Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh, đồng thời có thêm ~m~ truy vấn có một trong hai dạng như sau:

• ~1~ ~u~ ~v~ thêm cạnh ~(u,v)~ vào đồ thị.
• ~2~ ~u~ ~v~ in ra thời gian sớm nhất (chỉ số của truy vấn) để ~u~ và ~v~ liên thông.

Input

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5; 1 \le m \le 5*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~t,u,v~, nếu ~t = 1~ thì là dạng truy vấn thứ nhất, ngược lại là dạng thứ hai.

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả. Nếu hai đỉnh chưa liên thông, in ra ~-1~.

Scoring

Example

Sample Input

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

Sample Output

1
3
-1