Cho một đồ thị vô hướng gồm ~N~ đỉnh, ban đầu đồ thị này không có cạnh nào. Mỗi đỉnh thứ ~i~ được gán một màu ~c_i~.

Bạn cần thực hiện lần lượt ~Q~ thao tác, mỗi thao tác thuộc một trong hai loại sau:

• Loại ~1~: 1 x y — nối toàn bộ các đỉnh có màu ~x~ với toàn bộ các đỉnh có màu ~y~;

• Loại ~2~: 2 u v — đổi màu của toàn bộ các đỉnh ~i~ có ~c_i=u~ thành ~c_i=v~.

Sau khi thực hiện xong tất cả các thao tác, hãy in ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị.

Input

• Dòng đầu tiên chứa hai số nguyên ~N,Q~ ~(1 \leq N,Q \leq 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên ~c_1,c_2,\ldots,c_N~ — màu ban đầu của từng đỉnh ~(1 \leq c_i \leq N)~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~t,x,y~ mô tả các thao tác ~(1 \leq t \leq 2, 1 \leq x,y \leq N)~.

Output

• In ra ~N~ số nguyên, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~. Nếu không tồn tại đường đi, in ra ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

0 1 -1 1 2

Notes

• Ban đầu: chưa có cạnh nào;

• Thao tác 1 1 2: Nối toàn bộ đỉnh màu ~1~ với toàn bộ đỉnh màu ~2~ ⇒ Tạo cạnh giữa các đỉnh ~\{1,5\}~ với ~\{2,4\}~;

• Thao tác 2 3 2: Đổi toàn bộ đỉnh màu ~3~ thành màu ~2~ ⇒ Đỉnh ~3~ có màu ~2~;

• Thao tác 1 2 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~;

• Thao tác 1 1 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~.

Sau cùng, đường đi ngắn nhất từ đỉnh ~1~ đến các đỉnh khác là:

• Đỉnh ~1~ → chính nó: ~0~
• Đỉnh ~2~: ~1 \to 2~ (độ dài ~1~)
• Đỉnh ~3~: Không tồn tại đường đi (~-1~)
• Đỉnh ~4~: ~1 \to 4~ (độ dài ~1~)
• Đỉnh ~5~: ~1 \to 2 \to 5~ (độ dài ~2~)