SGAME4

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
vinhntndu
Dạng bài
Điểm: 500 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nông dân V.H.A có \(N\) khu vườn để chăn nuôi chú gà SPyofgame. Các khu vườn được kết nối với nhau bằng \(N-1\) con đường hai chiều, tức là chỉ có đúng một đường đi giữa hai khu vườn (giàu mà keo đây mà). Vì là một con gà béo tham lam nên SPyofgame đã đòi hỏi trên đường các con đường luôn phải có đồ ăn cho nó. Vì thế, V.H.A đã phải thực hiện các công việc sau:

  1. P x y: V.H.A sẽ chọn ra hai khu vườn và bỏ 1 nồi thóc dọc theo con đường nối hai khu vườn.
  2. Q x y: V.H.A sẽ phải trả lời trên đoạn đường nối hai khu vườn có bao nhiêu nồi thóc.

Input:

  • Dòng đầu tiên chứa hai số nguyên \(N, M (1 \leq M \leq 100000, 2 \leq N \leq 100000).\)
  • \(N-1\) dòng tiếp theo, mỗi dòng là hai số nguyên thể hiện hai đầu nối của một con đường.
  • \(M\) dòng cuối cùng, mỗi dòng là một truy vấn theo cấu trúc P x y hoặc Q x y \((1 \leq x,y \leq N)\).

Output:

  • Mỗi dòng là câu trả lời cho mỗi truy vấn Q theo thứ tự.

Example

Test 1

Input 
3 3
1 2
2 3
P 1 3
Q 2 3
Q 1 3
Output 
1
2

Bình luận