Cho đồ thị ban đầu có ~ n ~ đỉnh và 0 cạnh, các đỉnh được đánh số từ 1 đến ~ n ~. Bạn cần thực hiện lần lượt ~ m ~ truy vấn, mỗi truy vấn thuộc 1 trong 2 loại sau: 1. Cho một số nguyên ~ u ~ ~ (1≤u≤n) ~, hãy in ra độ dài đường đi ngắn nhất từ 1 đến ~ u ~. 2. Cho 2 số nguyên ~ u,v ~ ~ (1≤u,v≤n) ~, thêm cung ~ (u,v) ~ vào đồ thị.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương ~ n, m ~.
• ~ m ~ dòng tiếp theo, mỗi dòng ghi thông tin về một loại truy vấn

Giới hạn:

• ~ 1≤n≤1000 ~
• ~ 1≤m≤500000 ~

Kết quả

Với mỗi truy vấn loại 1 trong input, in ra độ dài đường đi ngắn nhất từ 1 đến ~u~, nếu trong đồ thị không có đường đi từ ~1~ đến ~u~ thì in ~-1~.

Ví dụ:

Input 1

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

Output 1

-1
3
2