(jsd.*)

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 \leq u \leq 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 \leq u,v \leq 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 \leq n \leq 1000\)

+ \(1 \leq m \leq 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	Output
4 7 1 4 2 1 2 2 2 3 2 3 4 1 4 2 2 4 1 4	-1 3 2