Một hệ thống website TOURGO quản lý vận chuyển hàng hóa trên toàn quốc được vận hành dựa trên máy chủ. Để đơn giản bài toán, ta đánh số các máy chủ từ đến , ban đầu máy chủ thứ quản lý dữ liệu khách hàng mang chỉ số . Biết rằng có kết nối trực tiếp giữa các cặp hai máy chủ khác nhau, hệ thống này đảm bảo giữa hai máy chủ bất kì luôn được kết nối trực tiếp hoặc gián tiếp (cấu trúc mạng dạng cây).
Vào một thời điểm nào đó, hai máy chủ được kết nối trực tiếp sẽ chia sẻ dữ liệu với nhau, cụ thể là nó sẽ đồng nhất dữ liệu với nhau. Khi đó, tập dữ liệu mà hai máy chủ này có được chính là hợp của hai tập dữ liệu của chúng trước đó. Ví dụ: tại một thời điểm, máy chủ A có tập dữ liệu khách hàng là còn máy chủ B có tập dữ liệu khách hàng là thì sau khi chia sẻ dữ liệu với nhau cả hai máy A và B có cùng tập dữ liệu khách hàng là .
Để kiểm tra tính ổn định và tốc độ phản hồi của hệ thống, nhóm Webu đã đưa ra các truy vấn để kiểm tra hệ thống gồm ba loại yêu cầu như sau:
S a b: Máy chủ và thực hiện chia sẻ dữ liệu, lưu ý rằng và luôn luôn là cặp máy chủ được kết nối trực tiếp với nhau.
Q a d: Kiểm tra xem máy chủ có chứa dữ liệu của khách hàng mang chỉ số hay không? Nếu có in ra “yes”, ngược lại in ra “no”.
C d: Đếm và đưa ra số lượng máy chủ có chứa dữ liệu của khách hàng mang chỉ số .
Có tất cả truy vấn loại S, truy vấn loại Q và C. Nhiệm vụ của bạn là hãy viết chương trình thực hiện các truy vấn của nhóm Webu.
Dữ liệu:
Dòng đầu tiên gồm hai số nguyên và ().
dòng tiếp theo, mỗi dòng biểu diễn một trong các truy vấn đã nêu ở trên.
Kết quả: Với mỗi truy vấn loại Q và C bạn hãy in kết quả ra trên một dòng.
Ví dụ:
Dữ liệu:
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
Kết quả:
no
yes
no
6
6
5
3
2
2
Giải thích:
Ban đầu: server 1 có {1}, 2 có {2}, ..., 6 có {6}.
S 1 2: server 1, 2 đều có {1,2}.
S 1 3: server 1, 2, 3 đều có {1,2,3}.
S 3 4: server 1, 2, 3, 4 đều có {1,2,3,4}.
Q 5 1: tập dữ liệu của máy chủ 5 lúc này đang là {5}, không chứa 1. Kết quả là no.
S 4 5: server 1, 2, 3, 4, 5 đều có {1,2,3,4,5}.
S 1 6: server 1, 2, 3, 4, 5, 6 đều có {1,2,3,4,5,6}.
Q 5 1: tập dữ liệu của máy chủ 5 lúc này là {1,2,3,4,5}, có chứa 1. Kết quả là yes.
Q 1 5: tập dữ liệu của máy chủ 1 lúc này là {1,2,3,4,5,6}, có chứa 5. Kết quả là yes. (Lưu ý: ví dụ gốc ghi no có thể bị nhầm, theo logic thì là yes).
C 1: tất cả 6 máy chủ đều có dữ liệu 1.
C 2: tất cả 6 máy chủ đều có dữ liệu 2.
C 3: 5 máy chủ (1,2,3,4,5) có dữ liệu 3.
C 4: 3 máy chủ (3,4,5) có dữ liệu 4.
C 5: 2 máy chủ (4,5) có dữ liệu 5.
C 6: 2 máy chủ (1,6) có dữ liệu 6.
Giới hạn:
Subtask 1 (10%): .
Subtask 2 (15%): Máy chủ 1 kết nối trực tiếp với các máy chủ .
Subtask 3 (15%): Máy chủ được kết nối trực tiếp với máy chủ khi và chỉ khi .
Subtask 4 (15%): Giả sử và máy chủ được kết nối trực tiếp với máy chủ , khi đó hoặc .
Subtask 5 (20%): Một máy chủ được kết nối trực tiếp với tối đa 5 máy chủ khác.
