고양이 또는 개

아들 JOI-kun은 애완동물을 키우는 것을 좋아합니다. 정원에는 1번부터 $N$번까지 번호가 붙은 $N$개의 오두막(hut)이 있고, 각 오두막에는 애완동물이 최대 한 마리만 있을 수 있습니다. 오두막들은 $N-1$개의 길로 양방향으로 연결되어 있으며, 임의의 두 오두막 사이는 길을 따라 이동할 수 있습니다.

JOI-kun은 고양이와 개를 키우고 싶지만, 둘이 자주 싸울까 걱정합니다. 각 오두막이 고양이, 개, 애완동물 없음 중 하나의 상태일 때, 정원의 위험도를 다음과 같이 정의합니다. 고양이와 개가 막히지 않은 길을 따라 만나지 못하도록 막아야 하는 길의 최소 개수입니다.

JOI-kun은 $Q$일 동안 정원을 사용할 계획을 세웁니다. 처음에는 어느 오두막에도 애완동물이 없습니다. 매일의 계획은 다음 중 하나입니다.

• cat: 애완동물이 없는 오두막 $v$에 새 고양이를 둔다.
• dog: 애완동물이 없는 오두막 $v$에 새 개를 둔다.
• neighbor: 오두막 $v$의 애완동물을 이웃에게 준다(그 뒤 오두막 $v$에는 애완동물이 없다).

부모인 여러분은 아들의 계획이 위험한지 확인해야 합니다. 매일 계획을 수행한 뒤의 정원 위험도를 구하세요.

첫 줄에 $N$이 주어집니다. $i+2$번째 줄($0 \le i \le N-2$)에는 $A_i$와 $B_i$가 주어지며, 오두막 $A_i$와 오두막 $B_i$ 사이에 길이 있다는 뜻입니다. 서로 다른 임의의 두 오두막은 길을 따라 이동할 수 있다고 보장됩니다.

다음 줄에는 $Q$가 주어집니다. $N+2+j$번째 줄($0 \le j \le Q-1$)에는 $T_j$와 $v_j$가 주어집니다. $j+1$일째 계획은 $T_j=1$이면 cat, $T_j=2$이면 dog, $T_j=3$이면 neighbor이며, 대상은 오두막 $v_j$입니다.

$j$를 $0$부터 $Q-1$까지 차례로, $j+1$일째 계획을 수행한 뒤의 위험도를 한 줄에 하나씩 출력합니다.

오두막이 5개이고 길이 4개인 정원을 생각해 봅시다. 길은 오두막 1과 2, 2와 3, 2와 4, 4와 5를 각각 잇습니다.

1. 먼저 3번 오두막에 고양이, 5번 오두막에 개를 둡니다. 2번과 4번 사이의 길을 막으면 고양이와 개가 만나지 못하므로 이때의 위험도는 1입니다.
2. 다음으로 2번 오두막에 새 고양이, 1번 오두막에 새 개를 둡니다. 2번과 4번 사이의 길과 1번과 2번 사이의 길을 막으면 만나지 못하므로 위험도는 2입니다.
3. 마지막으로 2번 오두막의 고양이를 이웃에게 줍니다. 2번과 3번 사이의 길만 막으면 되므로 위험도는 1입니다.