하늘 세금
시간 제한1초메모리 제한512 MB
수도가 계속 바뀌는 트리에서 어떤 도시가 수도로 가는 경로에 포함되면 그 도시가 세금을 담당한다. 수도를 옮기거나 특정 도시가 담당하는 도시 수를 물을 때 답한다.
문제
뉴 방콕은 하늘에 떠 있는 태국의 새 주다. 주가 공중에 떠 있도록 각 도시를 우주선 한 대가 떠받친다. 우주선이 모두 같은 방향으로 같은 속도로 움직이므로 주 전체의 구조는 그대로 유지된다.
도시는 하늘길로 이어져 있다. 하늘길은 두 도시를 잇는 공중 도로이고, 주민은 하늘길만 이용해 어느 도시에서 다른 어느 도시로든 오갈 수 있다. 도시 계획이 잘 되어 있어서 한 도시에서 다른 도시로 가는 단순 경로는 정확히 하나뿐이다. 즉 같은 하늘길을 두 번 지나는 경로는 없다.
이 주는 생긴 지 얼마 되지 않아 수도를 자주 옮긴다. 세금 규칙도 특이하다. 도시 에서 수도로 가는 경로가 도시 를 지나면 가 의 세금을 처리해야 한다. 경로의 양 끝인 와 수도도 경로에 포함되므로 모든 도시는 적어도 자기 자신의 세금을 처리한다. 그래서 한 도시가 여러 도시의 세금을 떠맡기도 한다.
주의 구조와 처음 수도, 질의 개수가 주어진다. 각 질의는 다음 둘 중 하나다.
- 수도를 도시 로 옮긴다.
- 도시 가 세금을 처리해야 하는 도시가 몇 개인지 답한다.
입력
첫 줄에 테스트 케이스 개수 가 주어진다. ()
각 테스트 케이스의 첫 줄에는 도시 수 , 질의 수 , 처음 수도 이 순서대로 주어진다. (, , )
다음 개 줄에는 하늘길 정보가 한 줄에 하나씩 주어진다. 각 줄은 두 정수 와 로 이루어지고, 도시 와 도시 가 하늘길로 이어져 있다는 뜻이다. (, , )
다음 개 줄에는 질의가 한 줄에 하나씩 주어진다. 각 줄은 두 정수 와 로 이루어진다. (, ) 가 이면 수도를 도시 로 옮기고, 가 이면 도시 가 세금을 처리해야 하는 도시의 개수를 묻는다.
출력
테스트 케이스와 질의는 입력에 주어진 순서대로 처리한다.
번째 테스트 케이스를 시작할 때 Case #I: 형식의 줄을 먼저 출력한다. 여기서 I는 테스트 케이스 번호다.
그다음 답을 요구하는 질의마다 답을 한 줄에 하나씩 출력한다. 수도를 옮기는 질의는 아무것도 출력하지 않는다.