You'd like to design a package manager on your own, and thus you'd like to resolve the dependency problem among packages. If package depends on package , then we must install package before package . Likewise, if we'd like to remove package , we also need to remove package . You know the dependency relations among the packages, and you may assume all packages other than package 0 will rely on exactly one package (package 0 does not rely on any other packages). There are no cycles in the dependency relation (like depends on , depends on , ..., depends on but depends on ), and of course no package depends on itself.
Now you'd like to know how many packages have their status changed upon installing or uninstalling a given package. Notice installing an installed package or uninstalling an uninstalled package will not change the status of any package.
The first line of the input is an integer representing the number of packages. The packages are numbered beginning with 0.
The next line has integers separated by a single space, representing the package that package depends on.
The next line contains an integer representing the number of queries. In the following lines, each line contains a query of form
install x or
uninstall x representing installing or uninstalling package . You need to maintain the status of each package. Initially, all packages are uninstalled. You need to output how many packages will change the status after the step, and then apply the (un)installation.
The output consists of lines. The -th line is an integer representing the number of packages whose status change at step .
Sample Input 1
7 0 0 0 1 1 5 5 install 5 install 6 uninstall 1 install 4 uninstall 0
Sample Output 1
3 1 3 2 3
Sample Input 2
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
Sample Output 2
1 3 2 1 3 1 1 1 0 1
|Test Case||Additional Constraints|
|3||we never uninstall a package|
|5||the package that package depends on is uniformly at random in . The package installed or uninstalled at each query is uniformly at random in .|