농장 관리

$N$개의 농장이 있고, 이 농장들을 양방향으로 잇는 $N-1$개의 도로가 있다. 임의의 두 농장 사이에는 정확히 하나의 경로만 존재한다. 즉, 농장과 도로는 트리를 이룬다. 농장에는 $1$번부터 $N$번까지 번호가 붙어 있다.

재현이는 도로를 따라 나무를 심으려고 한다. 작업은 쿼리로 주어지며, 쿼리는 두 종류이다.

• P u v: $u$번 농장과 $v$번 농장을 잇는 경로 위의 모든 도로에 나무를 한 그루씩 심는다.
• Q u v: $u$번 농장과 $v$번 농장을 잇는 경로 위의 도로에 심겨 있는 나무의 총 개수를 출력한다.

처음에는 어떤 도로에도 나무가 심겨 있지 않다. 주어지는 쿼리를 순서대로 처리하라.

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

이어지는 $N-1$개의 줄에는 각 도로가 잇는 두 농장의 번호가 한 줄에 하나씩 주어진다.

그다음 $M$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 각 쿼리는 문자 하나(P 또는 Q)와 두 정수 $u$, $v$로 이루어지며, 위에서 설명한 형식을 따른다.

각 Q 쿼리마다, 해당 경로 위의 도로에 심겨 있는 나무의 개수를 한 줄에 하나씩 출력한다.