Description

You decide to design your own package manager. Inevitably, you must handle dependencies between packages. If package $a$ depends on package $b$, then before installing package $a$, you must first install package $b$. Likewise, if you want to uninstall package $b$, you must uninstall package $a$.

Now you have obtained all dependency relations among packages. Moreover, due to your previous design, every package in your manager except package $0$ depends on exactly one package, and package $0$ depends on none. The dependency relations contain no cycles (i.e., there do not exist $m$ packages $a_1, a_2, \dots, a_m$ such that for $i < m$, $a_i$ depends on $a_{i+1}$, and $a_m$ depends on $a_1$).

You now need to write a dependency resolver for your package manager. According to user feedback, when installing or uninstalling a package, users want to quickly know how many packages will actually change their installation state as a result of the operation (that is, how many currently uninstalled packages will be installed by an install operation, or how many currently installed packages will be uninstalled by an uninstall operation). Your task is to implement this part.

Note that installing an already installed package, or uninstalling a package that is not installed, will not change any installation state. In this case, the number of packages whose installation state changes is $0$.

Input Format

The first line contains a positive integer $n$, the number of packages, numbered starting from $0$.
The second line contains $n - 1$ integers; the $i$-th integer denotes the package ID that package $i$ depends on.
Then a line with a positive integer $q$ follows, denoting the number of operations, in the following format:

• install x means install package $x$.
• uninstall x means uninstall package $x$.

Initially, all packages are not installed.

For each operation, you need to output how many packages will change their installation state because of this step, and then apply the operation (i.e., update the installation states you maintain).

Output Format

Output $q$ lines, each containing an integer, which is the answer for each query.

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

3
1
3
2
3

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

1
3
2
1
3
1
1
1
0
1

Hint

Initially, all packages are not installed.

To install package $5$, you need to install packages $0, 1, 5$.

After that, installing package $6$ only requires installing package $6$. At this point, packages $0, 1, 5, 6$ are installed.

Uninstalling package $1$ requires uninstalling packages $1, 5, 6$. Now only package $0$ remains installed.

Next, installing package $4$ requires installing packages $1, 4$. Now packages $0, 1, 4$ are installed. Finally, uninstalling package $0$ will uninstall all packages.

Constraints

::cute-table{tuack}

Translated by ChatGPT 5