하늘 세금

뉴 방콕은 하늘에 떠 있는 태국의 새 주다. 주가 공중에 떠 있도록 각 도시를 우주선 한 대가 떠받친다. 우주선이 모두 같은 방향으로 같은 속도로 움직이므로 주 전체의 구조는 그대로 유지된다.

도시는 하늘길로 이어져 있다. 하늘길은 두 도시를 잇는 공중 도로이고, 주민은 하늘길만 이용해 어느 도시에서 다른 어느 도시로든 오갈 수 있다. 도시 계획이 잘 되어 있어서 한 도시에서 다른 도시로 가는 단순 경로는 정확히 하나뿐이다. 즉 같은 하늘길을 두 번 지나는 경로는 없다.

이 주는 생긴 지 얼마 되지 않아 수도를 자주 옮긴다. 세금 규칙도 특이하다. 도시 $B$에서 수도로 가는 경로가 도시 $A$를 지나면 $A$가 $B$의 세금을 처리해야 한다. 경로의 양 끝인 $B$와 수도도 경로에 포함되므로 모든 도시는 적어도 자기 자신의 세금을 처리한다. 그래서 한 도시가 여러 도시의 세금을 떠맡기도 한다.

주의 구조와 처음 수도, 질의 개수가 주어진다. 각 질의는 다음 둘 중 하나다.

1. 수도를 도시 $U$로 옮긴다.
2. 도시 $U$가 세금을 처리해야 하는 도시가 몇 개인지 답한다.

첫 줄에 테스트 케이스 개수 $T$가 주어진다. ($T \le 10$)

각 테스트 케이스의 첫 줄에는 도시 수 $N$, 질의 수 $Q$, 처음 수도 $R$이 순서대로 주어진다. ($1 \le N \le 100000$, $1 \le Q \le 50000$, $1 \le R \le N$)

다음 $N - 1$개 줄에는 하늘길 정보가 한 줄에 하나씩 주어진다. 각 줄은 두 정수 $A$와 $B$로 이루어지고, 도시 $A$와 도시 $B$가 하늘길로 이어져 있다는 뜻이다. ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$)

다음 $Q$개 줄에는 질의가 한 줄에 하나씩 주어진다. 각 줄은 두 정수 $S$와 $U$로 이루어진다. ($0 \le S \le 1$, $1 \le U \le N$) $S$가 $0$이면 수도를 도시 $U$로 옮기고, $S$가 $1$이면 도시 $U$가 세금을 처리해야 하는 도시의 개수를 묻는다.

테스트 케이스와 질의는 입력에 주어진 순서대로 처리한다.

$I$번째 테스트 케이스를 시작할 때 Case #I: 형식의 줄을 먼저 출력한다. 여기서 I는 테스트 케이스 번호다.

그다음 답을 요구하는 질의마다 답을 한 줄에 하나씩 출력한다. 수도를 옮기는 질의는 아무것도 출력하지 않는다.