Description

长期以来，中央城的水供应一直没有问题。城市的排水系统呈现出一棵根树的形式：中央水库位于树根，房屋位于树叶。水通过沿着树的边缘运行的管道从中央水库流向房屋。每个房屋都能获得水。

突然，黑帮占领了一些房屋。作为市长，你非常担心，并想要赶走这些黑帮。因此，你希望停止向被黑帮占领的房屋供水。为此，你可以堵塞排水系统中的一些管道。如果从水库到某个房屋的路径上至少有一根管道被堵塞，那么该房屋将无法获得水。

你非常害怕这些黑帮，所以你决定堵塞最少数量的管道，以使其看起来像是意外。同时，你关心市民，因此对于选择的堵塞管道数量，你希望最小化没有黑帮且无法获得水的房屋数量。

不幸的是，黑帮可能会在一些房屋中出现和消失。因此，你询问科学家在每次黑帮位置变化后所需的最小堵塞管道数量以及没有黑帮且无法获得水的房屋的最小数量。

Input Format

输入的第一行包含两个整数 $n$ 和 $q$ —— 表示树中顶点的数量（代表排水系统）和黑帮位置变化的次数（$2 \le n \le 100 000$；$1 \le q \le 100 000$）。

第二行包含排水系统的描述：一个由 $n - 1$ 个整数 $p_{2}, p_{3}, \ldots, p_{n}$ 组成的序列，其中 $p_{i}$ 是顶点 $i$ 的父节点 $(1 \le p_{i} < i)$。中央水库位于顶点 $1$。

接下来的 $q$ 行表示黑帮位置的变化。每个变化可以是两种不同类型之一：

• + v —— 黑帮占领顶点 $v$ 处的房屋；
• - v —— 黑帮离开顶点 $v$ 处的房屋。

一开始所有房屋都没有被黑帮占领。所有变化形成了正确的序列：黑帮不能占领已经被占领的房屋，黑帮也不能离开未被占领的房屋。

Output Format

输出应包含 2q 个整数，每行两个：$c_{i}$ —— 最小堵塞管道数量，以及 $h_{i}$ —— 在选择的 $c_{i}$ 下没有黑帮且无法获得水的房屋的最小数量。

7 6
1 2 1 3 3 3
+ 4
+ 5
+ 6
+ 7
- 6
- 5

1 0
2 0
2 1
2 0
2 1
2 0

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。