eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Бандиты в центральном городе

Бандиты в центральном городе

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Долгое время в центральном городе не было проблем с водой. Канализация города представляет собой укоренившееся дерево: центральный резервуар находится у корня, а дома — у листьев. Вода из центрального резервуара течет в дома по трубам, идущим по краям дерева. В каждом доме есть доступ к воде.

Внезапно бандиты захватили часть домов. Как мэр города Вы очень обеспокоены и хотите выгнать бандитов. Итак, Вы хотите остановить поток воды к домам, захваченным гангстерами. Для этого можно засорить некоторые трубы канализации. Если на пути от резервуара к дому есть хотя бы одна забитая труба, в доме нет доступа к воде.

Вы очень боитесь бандитов, поэтому решили засорить минимальное количество труб, чтобы это выглядело как авария. При этом Вы заботитесь о горожанах, поэтому при выбранном количестве забитых труб Вы хотите минимизировать количество домов без бандитов и доступа к воде.

К сожалению, бандиты могли появляться и исчезать из некоторых домов. Итак, Вы спрашиваете ученых о минимально необходимом количестве забитых труб и минимально необходимом количестве домов без бандитов и доступа к воде после каждой смены местоположения бандитов.

Входные данные

Первая строка содержит два целых числа n и q~(2 \le n \le 10^5, 1 \le q \le 10^5) — количество вершин в дереве, представляющие канализацию, и количество изменений в местонахождении бандитов.

Вторая строка содержит описание канализации: последовательность из n - 1 целого числа p_2, p_3, ..., p_n, где p_i является родителем вершины i~(1 \le p_i < i). Центральный резервуар находится в вершине 1.

Следующие q строк описывают изменения в местонахождении гангстеров. Каждое изменение может быть одного из двух разных типов:

  • "+ v" — гангстеры захватывают дом в вершине v,

  • "- v" — гангстеры выходят из дома в вершине v.

Сначала все дома свободны от гангстеров. Все изменения образуют правильную последовательность: гангстеры не могут захватить дом, если он уже захвачен, и гангстеры не могут покинуть дом, если он не захвачен.

Выходные данные

Выведите 2q целых числа, по два в каждой строке: c_i — минимальное количество забитых труб и h_i — минимальное количество домов без бандитов и без доступа к воде для выбранного c_i.

Пример

Входные данные #1
7 6
1 2 1 3 3 3
+ 4
+ 5
+ 6
+ 7
- 6
- 5
Выходные данные #1
1 0
2 0
2 1
2 0
2 1
2 0
Источник 2016 ACM NEERC, Северный регион, Октябрь 22, Задача G