Trung tâm liên kết cụm

Bối cảnh và bài toán

Một trung tâm điều hành quản lý n nút dịch vụ. Ban đầu mỗi nút hoạt động như một cụm độc lập. Trong quá trình vận hành, hệ thống có thể thiết lập liên kết giữa hai nút; từ thời điểm đó, toàn bộ hai cụm chứa chúng được xem là một cụm thống nhất.

Đội vận hành cần đồng thời trả lời các câu hỏi về việc hai nút có thuộc cùng cụm hay không, kích thước cụm hiện tại của một nút và tổng số cụm còn lại. Số thao tác lớn nên việc quét lại toàn bộ hệ thống sau mỗi thay đổi là không khả thi.

Yêu cầu

Xử lý lần lượt q thao tác theo đúng thứ tự xuất hiện.

Input

• Dòng 1 chứa hai số nguyên n q.
• q dòng tiếp theo, mỗi dòng có một trong bốn dạng:
  • MERGE a b: thiết lập liên kết giữa hai nút a, b.
  • SAME a b: hỏi a và b hiện có cùng cụm hay không.
  • SIZE x: hỏi số nút trong cụm chứa x.
  • COUNT: hỏi tổng số cụm hiện tại.

Output

• Với mỗi lệnh SAME, in YES hoặc NO.
• Với mỗi lệnh SIZE, in kích thước cụm tương ứng.
• Với mỗi lệnh COUNT, in số cụm hiện tại.
• Lệnh MERGE không tạo output.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• 1 <= a, b, x <= n
• Có thể có lệnh MERGE giữa hai nút vốn đã cùng cụm.

Chấm điểm

Ví dụ 1

Input

5 9
COUNT
SAME 1 2
MERGE 1 2
SIZE 1
COUNT
MERGE 2 3
SAME 1 3
SIZE 3
COUNT

Output

5
NO
2
4
YES
3
3

Giải thích. Sau khi nối 1–2, số cụm giảm từ 5 xuống 4; nối tiếp 2–3 làm ba nút 1,2,3 nằm cùng một cụm.

Ví dụ 2

Input

3 6
MERGE 1 2
MERGE 1 2
COUNT
SIZE 2
SAME 2 3
SIZE 3

Output

2
2
NO
1

Giải thích. Lần MERGE thứ hai không thay đổi partition vì 1 và 2 đã cùng cụm.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.