Ai mà ngờ sách khoa học máy tính lại có thể nhàm chán đến thế! Bạn chẳng học được bao nhiêu, còn tấm huy chương BOI thì ngày càng xa tầm với. Nhưng khoan đã — ai nói bạn phải giành huy chương một cách công bằng?¹

Ban tổ chức BOI đã cho biết đề thi được cất trong một kho bí mật mà chỉ trưởng ban khoa học mới mở được, nên bạn không thể tiếp cận chúng. Tuy nhiên, lấy được dữ liệu kiểm thử trước cuộc thi có vẻ khả thi hơn, và chừng đó cũng đủ mang lại lợi thế.

Không may cho bạn, ban khoa học đã có biện pháp ngăn chặn gian lận. Họ chia dữ liệu kiểm thử thành \(N\) phần và phân phối chúng cho \(N\) máy chủ được đánh số từ \(1\) đến \(N\). Ban đầu, máy chủ \(i\) lưu phần dữ liệu \(i\). Các máy chủ được nối bằng \(N-1\) dây sao cho hai máy chủ bất kỳ đều được nối với nhau trực tiếp hoặc gián tiếp. Thỉnh thoảng, hai máy chủ chia sẻ dữ liệu: sau đó, cả hai cùng lưu chính xác những phần dữ liệu mà ít nhất một trong hai máy chủ đã lưu trước khi chia sẻ. Mỗi cặp máy chủ nối trực tiếp với nhau chia sẻ dữ liệu đúng một lần; các cặp không nối trực tiếp không chia sẻ dữ liệu với nhau.

Bạn được cho toàn bộ thứ tự các lần chia sẻ. Để phối hợp những lần xâm nhập, bạn muốn biết dữ liệu đang được phân bố như thế nào tại một số thời điểm giữa các lần chia sẻ. Cụ thể, bạn cần trả lời liệu một máy chủ có đang lưu một phần dữ liệu cho trước hay không, hoặc có bao nhiêu máy chủ đang lưu một phần dữ liệu cho trước.

Hãy viết chương trình trả lời các truy vấn đó khi biết thứ tự các lần chia sẻ và thời điểm của từng truy vấn.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(K\). Mỗi dòng trong \(N+K-1\) dòng tiếp theo có một trong các dạng sau:

• S a b: máy chủ \(a\) và máy chủ \(b\) chia sẻ toàn bộ dữ liệu của chúng.
• Q a d: truy vấn xem máy chủ \(a\) hiện có lưu phần dữ liệu \(d\) hay không.
• C d: truy vấn số máy chủ hiện đang lưu phần dữ liệu \(d\).

Có đúng \(N-1\) dòng bắt đầu bằng S và đúng \(K\) dòng bắt đầu bằng Q hoặc C.

Dữ liệu ra

Với mỗi truy vấn Q a d, in một dòng chứa yes nếu máy chủ \(a\) lưu phần dữ liệu \(d\) tại thời điểm truy vấn, hoặc no nếu không. Với mỗi truy vấn C d, in một dòng chứa một số nguyên là số máy chủ lưu phần dữ liệu \(d\) tại thời điểm truy vấn. In các câu trả lời theo thứ tự truy vấn; câu trả lời chỉ phụ thuộc vào những lần chia sẻ đã xảy ra trước truy vấn đó.

Ràng buộc

• \(1\le N,K\le120\,000\).
• Các máy chủ và các phần dữ liệu được đánh số từ \(1\) đến \(N\).
• \(N-1\) dây nối tạo thành một mạng liên thông; mỗi dây được dùng để chia sẻ dữ liệu đúng một lần.

Phân nhóm

1. \(5\) điểm: \(N\le4\,000\).
2. \(5\) điểm: máy chủ \(1\) nối trực tiếp với các máy chủ \(2,3,\ldots,N\).
3. \(10\) điểm: hai máy chủ \(A\) và \(B\) nối trực tiếp với nhau khi và chỉ khi \(|A-B|=1\).
4. \(20\) điểm: với hai máy chủ \(A\) và \(B\) thỏa \(A<B\), chúng nối trực tiếp với nhau khi và chỉ khi \(2A=B\) hoặc \(2A+1=B\).
5. \(25\) điểm: mỗi máy chủ nối trực tiếp với nhiều nhất \(5\) máy chủ khác.
6. \(35\) điểm: không có ràng buộc thêm.

Trong mỗi phân nhóm, bạn nhận được \(50\%\) số điểm của phân nhóm đó nếu giải đúng tất cả các bộ dữ liệu không có truy vấn đếm số máy chủ lưu một phần dữ liệu, tức là không có dòng nào bắt đầu bằng C. Trên CMS, các bộ dữ liệu này được hiển thị là “Group 1” của phân nhóm tương ứng.

Ví dụ

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

no
yes
no
6
6
5
3
2
2

4 4
S 1 2
S 1 3
S 3 4
Q 2 1
Q 2 2
Q 2 3
Q 2 4

yes
yes
no
no

Giới hạn

Thời gian: \(2\) giây. Bộ nhớ: \(512\) MiB.