이진 트리 쿼리

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

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

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

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

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

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

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ Q$ $C_1\ C_2\ \cdots\ C_N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$ $q_1$ $q_2$ $\vdots$ $q_Q$

$C_i=0$이면 $i$번 정점은 검은색이고, $C_i=1$이면 $i$번 정점은 흰색이다.

$j$번째 간선은 $u_j$번 정점과 $v_j$번 정점을 연결한다.

각 $q_j$는 1 $i$, 2 $i$, 3 $i$ 중 하나의 형식이다.

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

• $1 \le T \le 100$.
• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $C_i \in \{0,1\}$ ($1 \le i \le N$).
• $1 \le u_j < v_j \le N$ ($1 \le j < N$).
• 주어진 간선은 트리를 이룬다.
• 어떤 정점을 루트로 정해도 주어진 트리는 이진 트리이다.
• 모든 쿼리에서 $1 \le i \le N$이다.
• 각 케이스에는 3번 쿼리가 한 번 이상 주어진다.
• 모든 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 케이스에 대한 $Q$의 합은 $200\,000$ 이하이다.