TRONGSO Tìm trọng số đường đi

Cho cây N đỉnh. Ban đầu mỗi cạnh có trọng số là 0. Cho M truy vẫn thuộc một trong hai loại:

• P A B: tăng trọng số các cạnh trên đường đi nối giữa hai đỉnh A B lên 1.
• Q A B: tìm trọng số của con đường nối từ A đến B.

Yêu cầu: trả lời các truy vấn loại Q.

Input:

• Dòng 1: ghi hai số nguyên N và M. (2 <= N, M <= 100 000)
• N dòng tiếp theo, mỗi dòng ghi hai số nguyên A B thể hiện cạnh nối hai đỉnh A B.
• M dòng tiếp theo, mỗi dòng biểu diễn một truy vấn gồm ba kí tự. Kí tự đầu tiên có thể là P hoặc Q là loại truy vấn, tiếp đó ghi hai số nguyên A_i và Bi (1 <= A_i, B_i <= N).

Output: Mỗi dòng ghi câu trả lời cho truy vấn loại Q.

Input	Output
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