Ở vùng Midsommer xa xôi có một khu châu thổ xinh đẹp. Các con sông ở đây đều mang các dòng chảy acid nên người thường không thể bơi qua được. Ở vùng châu thổ này có rất nhiều hòn đảo cũng như các cây cầu nối một số cặp hòn đảo với nhau. Mỗi cây cầu được gán cho một độ nguy hiểm riêng, thể hiện mức độ rủi ro khi băng qua cây cầu đó.

Thám tử Richard Hradecki thường xuyên phải di chuyển qua lại giữa các hòn đảo để xử lý các vụ án mà anh nhận được. Trong tất cả các lộ trình khả thi, anh ấy luôn chọn lộ trình an toàn nhất - tức là một lộ trình sao cho độ nguy hiểm lớn nhất trong các cây cầu là nhỏ nhất có thể.

Richard luôn nhờ đến bạn trong việc tìm ra lộ trình an toàn nhất mỗi khi anh ấy cần di chuyển từ một hòn đảo bất kỳ đến một hòn đảo khác để phá án. Để đáp ứng yêu cầu của Richard, bạn phải liên tục xử lý ba loại sự kiện sau đây:

• Một cây cầu nối giữa hai hòn đảo vừa được xây dựng bởi các thành viên của một bộ lạc địa phương.
• Một cây cầu bị phá hủy.
• Richard nhờ bạn tìm ra lộ trình an toàn nhất giữa hai hòn đảo.

Input

Dòng đầu chứa hai số nguyên \(N\) và \(Q\) \((2\) \(\leq\) \(N\) \(\leq\) \(10^5,\) \(1\) \(\leq\) \(Q\) \(\leq\) \(10^5)\) thể hiện số lượng các hòn đảo (được đánh số \(0,\) \(1,\) \(2,\) \(...,\) \(N\) \(−\) \(1)\) và số lượng sự kiện.

Mỗi dòng trong \(Q\) dòng tiếp theo thể hiện một sự kiện diễn ra ở vùng châu thổ, và được trình bày theo một trong các dạng:

• \(0\) \(X\) \(Y\) \(V:\) một cây cầu nối giữa hòn đảo \(X\) và hòn đảo \(Y\) vừa được xây dựng với độ nguy hiểm \(V\) \((0\) \(\leq\) \(V\) \(<\) \(10).\)
• \(1\) \(X\) \(Y:\) cây cầu nối giữa hòn đảo \(X\) và hòn đảo \(Y\) vừa bị phá hủy.
• \(2\) \(X\) \(Y:\) Richard nhờ bạn tìm ra lộ trình an toàn nhất từ hòn đảo \(X\) đến hòn đảo \(Y.\)

Trong tất cả các sự kiện, \(X\) và \(Y\) luôn thể hiện một cặp đảo hợp lệ \((0\) \(\leq\) \(X,\) \(Y\) \(<\) \(N\) và \(X\) \(\neq\) \(Y).\) Dữ liệu đảm bảo có tối đa một cây cầu nối hai hòn đảo bất kỳ và bất kỳ cây cầu nào cũng đều tồn tại trong thời điểm nó bị phá hủy.

Output

• Với mỗi sự kiện loại \(2,\) in ra một số nguyên \((\)trên một dòng riêng biệt\()\) thể hiện độ nguy hiểm cao nhất trong lộ trình tìm được. Nếu không tồn tại lộ trình nào từ \(X\) đến \(Y,\) in ra \(−1.\)

Example

6 15
0 1 2 1
2 1 4
2 1 5
0 2 3 2
2 1 4
2 1 5
0 3 4 3
2 1 4
2 1 5
0 4 5 4
2 1 4
2 1 5
1 4 5
2 1 4
2 1 5

-1
-1
-1
-1
3
-1
3
4
3
-1

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

4
4

Nguồn bài: CERC 2018