Cats or Dogs

Your son, JOI-kun, likes to have pets. There are $N$ huts for a pet, numbered 1 through $N$, in your house garden. There are $N-1$ paths connecting huts in both directions, and for any two huts, it is possible to move between them along some paths. Each hut can have at most one pet.

JOI-kun wants to have cats and dogs, but he is worried that they would often fight each other. For a situation where each hut has one of three states (a cat, a dog, or no pet), the danger level of the garden is defined as the minimum number of paths that must be blocked so that no cat and no dog can meet by moving along unblocked paths.

JOI-kun makes a plan to use the garden for $Q$ days. Initially, no hut has a pet. The plan on each day is one of the following:

• cat: Give a new cat to hut $v$, which currently has no pet.
• dog: Give a new dog to hut $v$, which currently has no pet.
• neighbor: Give the pet in hut $v$ to the neighbor (so hut $v$ has no pet afterward).

You, as a parent, need to check whether your son's plan is dangerous. For each day, find the danger level of the garden after that day's plan.

The first line contains $N$. Line $i+2$ (for $0 \le i \le N-2$) contains $A_i$ and $B_i$, meaning there is a path between huts $A_i$ and $B_i$. It is guaranteed that any two distinct huts are connected by some sequence of paths.

The next line contains $Q$. Line $N+2+j$ (for $0 \le j \le Q-1$) contains $T_j$ and $v_j$. The plan on day $j+1$ is cat if $T_j=1$, dog if $T_j=2$, and neighbor if $T_j=3$, applied to hut $v_j$.

For each $j$ from $0$ to $Q-1$, print on its own line the danger level after the plan on day $j+1$.

Consider a garden with 5 huts and 4 paths, connecting hut 1 with hut 2, hut 2 with hut 3, hut 2 with hut 4, and hut 4 with hut 5.

1. First, hut 3 gets a cat and hut 5 gets a dog. Blocking the path between hut 2 and hut 4 keeps the cat and the dog apart, so the danger level is 1.
2. Next, hut 2 gets a new cat and hut 1 gets a new dog. Blocking the path between hut 2 and hut 4 and the path between hut 1 and hut 2 keeps them apart, so the danger level is 2.
3. Finally, the cat in hut 2 is given to the neighbor. Only the path between hut 2 and hut 3 needs to be blocked, so the danger level is 1.