Sky Tax

New Bangkok is a newly built province of Thailand that floats in the sky. To keep the province in the air, one spaceship holds up each city. All the spaceships move in the same direction at the same speed, so the structure of the province stays still.

The cities are connected by sky ways. A sky way is a floating road between two cities, and a citizen can travel from any city to any other city using sky ways alone. Urban planning is thorough, so between one city and another there is exactly one simple route, meaning no route uses the same sky way twice.

The province is new and moves its capital often. Its tax rule is unusual: if the route from city $B$ to the capital passes through city $A$, then $A$ must handle the tax of $B$. The route includes both of its endpoints, $B$ and the capital, so every city handles at least its own tax. One city can end up handling the taxes of many cities.

You are given the structure of the province, the initial capital, and a number of queries. Each query is one of the following.

1. Move the capital to city $U$.
2. Report how many cities city $U$ has to handle taxes for.

The first line contains the number of test cases $T$. ($T \le 10$)

The first line of each test case contains the number of cities $N$, the number of queries $Q$, and the initial capital $R$, in that order. ($1 \le N \le 100000$, $1 \le Q \le 50000$, $1 \le R \le N$)

Each of the next $N - 1$ lines describes one sky way with two integers $A$ and $B$, meaning city $A$ and city $B$ are connected by a sky way. ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$)

Each of the next $Q$ lines describes one query with two integers $S$ and $U$. ($0 \le S \le 1$, $1 \le U \le N$) If $S$ is $0$, move the capital to city $U$. If $S$ is $1$, report the number of cities that city $U$ has to handle taxes for.

Process the test cases and the queries in the order they appear in the input.

At the start of test case $I$, print a line of the form Case #I:, where I is the test case number.

Then print the answer to each query that asks for one, one answer per line. A query that moves the capital prints nothing.