Một khu rừng có N con thú, ban đầu mỗi con sống riêng lẻ. Khi hai con thú gặp nhau và kết bạn, bầy đàn của chúng hợp nhất thành một. Có Q sự kiện:

• 1 u v: hai con thú u và v kết bạn (gộp bầy).
• 2 u: in ra kích thước của bầy đàn mà u đang thuộc về.

Đầu vào

• Dòng đầu chứa hai số nguyên N (1 ≤ N ≤ \(10^5\)) và Q (1 ≤ Q ≤ \(10^5\)).
• Q dòng tiếp theo, mỗi dòng mô tả một sự kiện.

Đầu ra

Với mỗi sự kiện loại 2, in kích thước bầy.

Ví dụ

Input:
6 5
1 1 2
1 3 4
2 2
1 2 3
2 5

Output:
2
4
1

Ràng buộc & Subtasks