Cho một cây ban đầu có ~ n ~ đỉnh và ~ n-1 ~ cạnh, người ta xóa hết các cạnh của cây, sau đó thực hiện ~ q ~ truy vấn, mỗi truy vấn thuộc một trong hai loại:

• **Loại 1: ** Cho bởi bộ 4 số ~ (1,u,v,w) ~ nghĩa là truy vấn thực hiện thêm cạnh có trong số ~ w ~ giữa hai đỉnh ~ u,v ~;
• **Loại 2: ** Cho bởi bộ ba số ~ (2,u,v) ~. Hỏi độ dài đường đi ngắn nhất từ đỉnh ~ u ~ đến đỉnh ~ v ~ hiện tại bằng bao nhiêu? Nếu không có đường đi thì in ~ -1 ~.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên ~ n,q ~;
• ~ q ~ dòng tiếp theo mỗi dòng ghi một truy vấn (có thể là truy vấn loại 1 hoặc loại 2)

Kết quả

In ra kết quả với mỗi truy vấn loại 2 theo đúng thứ tự trong dữ liệu vào

Ràng buộc

• ~ 1 ≤ n,q ≤2.10^5 ~
• ~ 1 ≤ w ≤ 10^4 ~

Ví dụ:

Input 1

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

Output 1

-1
8
7
12