Trồng Cỏ Trên Cây

Cho cây $N$ đỉnh và $M$ thao tác:

• P $u$ $v$: Cộng $1$ vào mọi cạnh trên đường đi từ $u$ đến $v$.
• Q $u$ $v$: In giá trị hiện tại của cạnh nối $u$ và $v$ ($u$ và $v$ kề nhau).

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$
• $N-1$ dòng tiếp theo: Hai số nguyên $A_i,B_i$ — cạnh của cây
• $M$ dòng tiếp theo: Mỗi dòng có dạng P u v hoặc Q u v

Dữ liệu ra

• Với mỗi thao tác Q, in ra một số nguyên.

Ràng buộc

• $2\le N\le 100000$
• $1\le M\le 100000$

Ví dụ