Долгое время в центральном городе не было проблем с водой. Канализация города представляет собой укоренившееся дерево: центральный резервуар находится у корня, а дома — у листьев. Вода из центрального резервуара течет в дома по трубам, идущим по краям дерева. В каждом доме есть доступ к воде.
Внезапно бандиты захватили часть домов. Как мэр города Вы очень обеспокоены и хотите выгнать бандитов. Итак, Вы хотите остановить поток воды к домам, захваченным гангстерами. Для этого можно засорить некоторые трубы канализации. Если на пути от резервуара к дому есть хотя бы одна забитая труба, в доме нет доступа к воде.
Вы очень боитесь бандитов, поэтому решили засорить минимальное количество труб, чтобы это выглядело как авария. При этом Вы заботитесь о горожанах, поэтому при выбранном количестве забитых труб Вы хотите минимизировать количество домов без бандитов и доступа к воде.
К сожалению, бандиты могли появляться и исчезать из некоторых домов. Итак, Вы спрашиваете ученых о минимально необходимом количестве забитых труб и минимально необходимом количестве домов без бандитов и доступа к воде после каждой смены местоположения бандитов.
Первая строка содержит два целых числа n и q (2≤n≤105,1≤q≤105) — количество вершин в дереве, представляющие канализацию, и количество изменений в местонахождении бандитов.
Вторая строка содержит описание канализации: последовательность из n−1 целого числа p2,p3,...,pn, где pi является родителем вершины i (1≤pi<i). Центральный резервуар находится в вершине 1.
Следующие q строк описывают изменения в местонахождении гангстеров. Каждое изменение может быть одного из двух разных типов:
"+v" — гангстеры захватывают дом в вершине v,
"−v" — гангстеры выходят из дома в вершине v.
Сначала все дома свободны от гангстеров. Все изменения образуют правильную последовательность: гангстеры не могут захватить дом, если он уже захвачен, и гангстеры не могут покинуть дом, если он не захвачен.
Выведите 2q целых числа, по два в каждой строке: ci — минимальное количество забитых труб и hi — минимальное количество домов без бандитов и без доступа к воде для выбранного ci.