N개의 농장과 농장을 양방향으로 연결하는 N-1개의 도로가 있다. 임의의 두 농장 사이에는 하나의 경로만 존재한다. 농장은 1번부터 N번까지 번호가 매겨져 있다.

농장을 관리하는 재현이는 도로에 나무를 심기로 결정했다. 나무를 심는 과정은 쿼리로 이루어져 있으며, 쿼리는 총 2가지가 존재한다.

• P u v: u번 농장과 v번 농장 사이의 경로에 존재하는 모든 도로에 나무를 하나씩 심는다.
• Q u v: u번 농장과 v번 농장 사이의 도로에 존재하는 나무의 개수를 출력한다.

초기에 나무는 한 그루도 심겨져 있지 않다. 쿼리를 수행해보자.

입력 형식

첫째 줄에 농장의 수 N과 쿼리의 수 M(1 ≤ N, M ≤ 100,000)이 주어진다.

둘째 줄부터 N-1개의 줄에는 도로가 연결하는 농장의 번호가 주어진다.

다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 쿼리는 한 개의 문자 w와 두 개의 정수 u, v로 이루어져 있고, 문제에서 설명한 형식이다.

출력 형식

쿼리 Q가 주어질 때 마다, 나무의 개수를 출력한다.

예제 입력

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