Pet Garden Danger Level

JOI-kun loves pets and has a garden with N houses numbered from \(1\) to \(N\) where pets can be kept. The houses are connected by \(N-1\) bidirectional paths forming a tree, so that any two houses are connected by a unique simple path.

Each house may be empty or may contain a single pet – either a cat or a dog. JOI‐kun is going to carry out a plan over \(Q\) days. Initially, all houses are empty. On each day one of the following operations is performed on a house \(v\):

• cat(v): In an empty house \(v\), a cat is added.
• dog(v): In an empty house \(v\), a dog is added.
• neighbor(v): The pet in house \(v\) is sent to a neighbor, so house \(v\) becomes empty.

After each day's operation, you must compute the garden's danger level. The danger level is defined as the sum, over every cat and every dog in the garden, of the number of roads on the unique path connecting them. In other words, if a cat is in house \(u\) and a dog is in house \(v\), their contribution is the distance (i.e. the number of edges) between \(u\) and \(v\). The overall danger level is the sum of these contributions for all cat–dog pairs.

This is an interactive problem. You are required to implement the following functions:

• initialize(N, A, B): Called first to initialize the garden. Here N is the number of houses, and arrays A and B (each of length \(N-1\)) indicate that there is a bidirectional path between houses \(A_i\) and \(B_i\) for \(0 \le i \le N-2\). It is guaranteed that the houses form a tree.
• cat(v): Add a cat to an empty house \(v\) and return the garden's danger level after the update.
• dog(v): Add a dog to an empty house \(v\) and return the garden's danger level after the update.
• neighbor(v): Remove the pet from house \(v\) (sending it to a neighbor) and return the updated danger level.

Note: All indices are 1-indexed. It is guaranteed that the operations are valid (i.e. a pet is only added to an empty house, and removal is only done in a house that currently contains a pet).

inputFormat

This is an interactive problem. The interaction begins with a call to initialize(N, A, B) where \(N\) is the number of houses and arrays A and B describe the \(N-1\) edges of the tree. Then, for \(Q\) days, one of the three functions cat(v), dog(v), or neighbor(v) is called. Each function should return the current danger level after performing the update.

For offline testing purposes, the input is given in the following format:

N
A0 B0
A1 B1
... (N-2 more lines)
Q
op1 v1
op2 v2
...
opQ vQ

where each op is one of cat, dog, or neighbor.

outputFormat

After each operation (i.e. each call to cat, dog, or neighbor), output the current danger level (an integer) on a separate line.

sample

3
1 2
2 3
5
cat 1
dog 3
cat 2
neighbor 1
dog 1

0
2
3
1
2