Canada có \(N\) thành phố được đánh số từ \(1\) đến \(N\) và \(N-1\) đường cao tốc được đánh số từ \(1\) đến \(N-1\). Mỗi đường cao tốc nối hai thành phố và có thể đi theo cả hai chiều. Mạng lưới đường cao tốc được thiết kế sao cho có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác bằng cách đi qua một số đường cao tốc. Nói cách khác, \(N\) thành phố và \(N-1\) đường cao tốc tạo thành một cây.

Bạn được bổ nhiệm làm giám đốc trung tâm thông tin ùn tắc giao thông và phải quản lý thông tin ùn tắc của mạng lưới đường cao tốc này.

Với mỗi đường trong số \(N-1\) đường cao tốc, trung tâm quản lý thời gian cần để đi từ thành phố ở đầu này đến thành phố ở đầu kia theo từng chiều. Chẳng hạn, trong hình dưới đây, các cặp thành phố \(1\) và \(3\), \(3\) và \(4\), \(2\) và \(3\) được nối bằng đường cao tốc. Trung tâm quản lý thời gian đi từ thành phố \(i\) đến thành phố \(j\) cho từng cặp sau:

Lưu ý rằng thời gian đi theo hai chiều của cùng một đường cao tốc không nhất thiết bằng nhau.

Ngoài việc lưu trữ dữ liệu, trung tâm còn thực hiện hai công việc sau.

Thỉnh thoảng, trung tâm nhận được một bản tin ùn tắc gồm ba số nguyên dương \(r\), \(s\), \(t\). Bản tin này cho biết thời gian đi theo chiều thuận của đường cao tốc \(r\) là \(s\), còn thời gian đi theo chiều ngược là \(t\). Chiều thuận là chiều đi từ thành phố có số hiệu nhỏ hơn đến thành phố có số hiệu lớn hơn trong hai đầu của đường cao tốc; chiều ngược là chiều còn lại. Trung tâm cập nhật dữ liệu theo bản tin này.

Trung tâm cũng có thể nhận được một cuộc gọi hỏi thông tin, được biểu diễn bởi hai số nguyên dương \(x\), \(y\). Khi đó, dựa trên dữ liệu hiện tại, trung tâm phải tính và trả lời thời gian cần để đi từ thành phố \(x\) đến thành phố \(y\).

Yêu cầu

Cho dãy các bản tin ùn tắc và yêu cầu hỏi thông tin trong một ngày, gọi chung là các truy vấn, theo thứ tự thời gian. Hãy viết chương trình in đáp án cho từng yêu cầu hỏi thông tin. Trước khi nhận bản tin ùn tắc đầu tiên, thời gian đi theo mỗi chiều của tất cả \(N-1\) đường cao tốc đều bằng \(1\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách. \(M\) là tổng số bản tin ùn tắc và yêu cầu hỏi thông tin.
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(p_i\), \(q_i\), cách nhau bởi dấu cách, cho biết đường cao tốc \(i\) nối thành phố \(p_i\) và thành phố \(q_i\).
• Mỗi dòng trong \(M\) dòng tiếp theo mô tả một truy vấn theo một trong hai dạng I r s t hoặc Q x y, với các thành phần cách nhau bởi dấu cách.

Truy vấn I r s t là bản tin ùn tắc: cập nhật thời gian đi theo chiều thuận của đường cao tốc \(r\) thành \(s\) và theo chiều ngược thành \(t\). Truy vấn Q x y yêu cầu thời gian đi từ thành phố \(x\) đến thành phố \(y\); hai thành phố này khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn số dòng bằng số truy vấn Q trong dữ liệu vào. Dòng thứ \(i\) chứa một số nguyên là đáp án cho yêu cầu hỏi thông tin thứ \(i\).

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(4\) giây, bộ nhớ \(256\) MB.

• \(2\le N\le 100\,000\).

• \(1\le M\le 100\,000\).
• \(1\le p_i<q_i\le N\) với mọi \(1\le i\le N-1\).
• Các thành phố và đường cao tốc tạo thành một cây.
• Trong mỗi truy vấn I r s t: \(1\le r\le N-1\), \(1\le s\le 1\,000\), \(1\le t\le 1\,000\).
• Trong mỗi truy vấn Q x y: \(1\le x,y\le N\) và \(x\ne y\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(16\) nhóm kiểm thử, mỗi nhóm \(5\) điểm và chứa \(1\) bộ dữ liệu, cùng \(2\) nhóm kiểm thử, mỗi nhóm \(10\) điểm và chứa \(2\) bộ dữ liệu. Có tất cả \(20\) bộ dữ liệu. Chỉ nhận điểm của một nhóm khi chương trình cho kết quả đúng trên tất cả các bộ dữ liệu trong nhóm, kết thúc bình thường (trả về mã \(0\)) và tuân thủ giới hạn thời gian, bộ nhớ.

• Các bộ kiểm thử có tổng cộng \(20\) điểm thỏa mãn \(N\le 1\,000\) và \(M\le 1\,000\).
• Các bộ kiểm thử có tổng cộng \(50\) điểm thỏa mãn: từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác đều có thể đi qua không quá \(1\,000\) đường cao tốc.

Ví dụ

4 5
1 3
3 4
2 3
I 1 7 9
Q 2 4
I 3 12 11
Q 2 4
Q 4 2

2
13
12