이진 트리 쿼리

$N$개의 정점으로 이루어진 트리 $T$가 주어진다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있으며, 각 정점은 검은색 또는 흰색이다.

$T$는 이진 트리이다. 처음에 $T$의 루트는 $1$번 정점이다.

다음 쿼리를 처리하는 프로그램을 작성하라.

• 1 $i$: $T$의 루트를 $i$번 정점으로 바꾼다. 어떤 정점을 루트로 정해도 $T$가 이진 트리임이 보장된다.
• 2 $i$: $i$번 정점의 색을 바꾼다. 흰색은 검은색으로, 검은색은 흰색으로 바뀐다.
• 3 $$: 현재 루트를 기준으로 번 정점을 루트로 하는 서브트리의 흰색 정점 수를 라 하자. 또한 번 정점부터 현재 루트까지의 경로에 속한 흰색 정점 수를 라 하자. 이때 를 출력한다. 경로에는 양 끝점이 모두 포함된다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 3번 쿼리에 대해, 쿼리의 답을 한 줄에 하나씩 출력한다.

• $1 \le T \le 100$.
• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.