Nông dân Hạo có \(N\) đồng cỏ \((2 \le N \le 10^5)\) được kết nối với nhau bởi \(N-1\) con đường hai chiều, đảm bảo rằng có một đường đi duy nhất giữa bất kỳ hai đồng cỏ nào. Bessie, một con bò yêu thích gặm cỏ, thường phàn nàn về việc thiếu cỏ trên các con đường giữa các đồng cỏ.

Nông dân Hạo muốn trồng cỏ trên các con đường và thực hiện việc này qua \(M\) bước \((1 \le M \le 10^5)\). Ở mỗi bước, một trong hai việc sau sẽ xảy ra:

• Nông dân Hạo chọn hai đồng cỏ và trồng một đám cỏ dọc theo mỗi con đường giữa hai đồng cỏ đó.
• Bessie hỏi về số lượng đám cỏ trên một con đường cụ thể, và Nông dân Hạo phải trả lời. Nông dân Hạo là người đếm rất kém, vì vậy hãy giúp anh trả lời các câu hỏi của Bessie!

Dữ liệu vào

• Dòng \(1\): Hai số nguyên \(N\) và \(M\) (số đồng cỏ và số bước).
• Dòng \(2\) đến \(N\): Mỗi dòng chứa hai số nguyên, mô tả các đầu mút của một con đường.
• Dòng \(N+1\) đến \(N+M\): Mỗi dòng mô tả một bước:
  • Bắt đầu bằng ký tự 'P' hoặc 'Q'.
  • Nếu là 'P', tiếp theo là hai số \(A_i\) và \(B_i\), cho biết Nông dân Hạo đang trồng cỏ.
  • Nếu là 'Q', tiếp theo là hai số \(A_i\) và \(B_i\), mô tả câu hỏi của Bessie.

Dữ liệu ra

• Mỗi dòng chứa câu trả lời cho một truy vấn của Bessie (truy vấn loại 'Q'), theo thứ tự xuất hiện trong đầu vào.

Input 1

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

Output 1

2
1
2