Software Package Dependency Manager

You are designing your own software package manager. One unavoidable aspect is resolving the dependency issues between packages. If package \(a\) depends on package \(b\), then you must install \(b\) before installing \(a\). Similarly, if you wish to uninstall package \(b\), you must first uninstall package \(a\).

You are given the dependency information for all packages. Moreover, due to previous work, every package in the manager (except package \(0\)) depends on exactly one package, while package \(0\) depends on no package. Furthermore, there are no cycles in the dependency relationships (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\)).

Your task is to implement the dependency resolver. Users want to know, when installing or uninstalling a package, how many packages have their installation status changed (i.e. installing a package will install all not-yet-installed packages in its dependency chain, and uninstalling a package will remove that package and all packages that depend on it). Note that installing an already installed package or uninstalling a package that is not installed does not change the status of any package (and the result should be \(0\)).

Input/Output Details

The package manager contains \(n\) packages numbered \(0\) through \(n-1\). Package \(0\) has no dependency, while each package \(i\) (for \(1 \leq i \leq n-1\)) depends on exactly one package. The dependency information is given on one line for packages \(1\) through \(n-1\); the \(i\)-th number (0-indexed for packages \(1,2,\dots\)) indicates the package that package \(i\) depends on.

Then, there are \(q\) operations. Each operation is in one of the following formats:

• install x: Install package \(x\). Installing a package automatically installs all its dependencies (if they are not already installed). If a package is already installed, nothing happens.
• uninstall x: Uninstall package \(x\) along with any packages that (directly or indirectly) depend on \(x\). If package \(x\) is not installed, nothing happens.

For each operation, output the number of packages that actually changed state as a result of that operation.

inputFormat

The first line contains two integers \(n\) and \(q\) representing the number of packages and the number of operations respectively.

The second line contains \(n-1\) integers. The \(i\)-th integer (for \(i=1\) to \(n-1\)) indicates the package that package \(i\) depends on. (Package 0 has no dependency.)

The following \(q\) lines each contain an operation in one of the formats:

• install x
• uninstall x

outputFormat

For each operation, output a single line with an integer indicating how many packages were installed or uninstalled as a result of that operation.

sample

5 5
0 1 1 2
install 4
install 3
uninstall 1
install 3
uninstall 0

4
1
4
2
3

</p>