Nông dân John có \(N\) đồng cỏ cằn cỗi (\(2 \le N \le 100\,000\)) được nối với nhau bởi \(N-1\) con đường hai chiều, sao cho giữa hai đồng cỏ bất kỳ có đúng một đường đi. Bessie, một chú bò rất yêu thích thời gian gặm cỏ, thường phàn nàn rằng trên những con đường giữa các đồng cỏ không có cỏ. Nông dân John rất yêu quý Bessie, và hôm nay cuối cùng ông cũng sẽ trồng cỏ trên các con đường. Ông sẽ thực hiện việc này bằng một quy trình gồm \(M\) bước (\(1 \le M \le 100\,000\)).

Ở mỗi bước, một trong hai việc sau sẽ xảy ra:

• FJ chọn hai đồng cỏ và trồng một mảng cỏ dọc theo mỗi con đường nằm trên đường đi giữa hai đồng cỏ đó; hoặc
• Bessie hỏi có bao nhiêu mảng cỏ trên một con đường cụ thể, và Nông dân John phải trả lời câu hỏi của cô.

Nông dân John đếm rất kém — hãy giúp ông trả lời các câu hỏi của Bessie!

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách, mô tả hai đầu mút của một con đường.
• \(M\) dòng tiếp theo; dòng thứ \(i\) mô tả bước thứ \(i\). Ký tự đầu tiên của dòng là P hoặc Q, cho biết FJ đang trồng cỏ hay chỉ thực hiện truy vấn. Theo sau là hai số nguyên \(A_i\) và \(B_i\) (\(1 \le A_i,B_i \le N\)) cách nhau bởi dấu cách, mô tả hành động hoặc truy vấn của FJ.

Dữ liệu ra

• Mỗi dòng chứa câu trả lời cho một truy vấn, theo đúng thứ tự các truy vấn xuất hiện trong dữ liệu vào.

Ví dụ

4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4

2
1
2

Nguồn

USACO 2011 December Contest, Gold Division — Grass Planting

Tác giả đề: Travis Hance, 2011.