문제

개의 정점으로 이루어진 트리 가 주어진다. 는 이진 트리이며, 따라서 각 정점마다 자식 노드의 개수가 2개를 넘지 않는다. 정점은 번부터 번까지 번호가 매겨져 있고, 정점의 색은 검은색 또는 흰색이다. 초기에 의 루트는 번 정점이다.

이하의 쿼리를 처리하는 프로그램을 작성하라.

• 1 i: 의 루트를 로 바꾼다. 어떠한 정점을 루트로 바꾼 트리도 이진 트리임이 보장된다.
• 2 i: 번 정점의 색을 바꾼다. (흰색 → 검정색, 검정색 → 흰색)
• 3 i: 에서, 번 정점을 루트로 하는 서브트리의 흰색 정점의 개수를 , 번 정점부터 루트까지의 경로에 속한 모든(와 루트를 포함한다) 흰색 정점의 개수를 라고 할 때, 를 출력한다.

입력

첫 번째 줄에 과 쿼리의 개수 가 주어진다. ,

두 번째 줄에 개의 정점의 색상을 나타내는 숫자가 주어진다. 번째 숫자가 이면 번 정점의 색상이 검은색임을 뜻하고, 이면 흰색임을 뜻한다.

세 번째 줄부터 개의 줄에는 각 간선이 연결하는 두 정점 번호 가 주어진다.

그 다음 줄부터 개의 줄에 걸쳐, 각 줄마다 쿼리가 주어진다.

어떠한 정점을 루트로 바꾸어도 새로 만들어진 트리가 이진 트리임이 보장되는 입력만 주어진다.

출력

3번 쿼리가 주어질 때마다, 한 줄에 하나씩 쿼리의 답을 출력한다. 3번 쿼리는 한 번 이상 주어진다.