Мальчик Серёжа почти закончил университет. Осталось только сдать последнюю сессию и защитить диплом. Сессия, прямо скажем, — это не проблема: Серёжа уже сдавал её в прошлом году, а вот диплом — задача непростая.
Серёжа пару лет назад уже выбрал тему диплома: это «Dynamic 2-Connectivity Problem». В такой задаче присутствует динамически меняющийся граф, и нужно быстро отвечать на запрос «количество мостов в графе в текущий момент времени».
Серёжа придумал несколько решений. В одном из них, наиболее простом для реализации, возникла одна несколько неприятная подзадача. Серёжа написал код, но тот оказался сложным и длинным...
И тут ему стало интересно, а вдруг есть более простая реализация? Более короткая и не менее быстрая. Для скорейшего получения ответа на столь любопытный вопрос решено было дать задачу на ближайший чемпионат родного университета.
До предзащиты осталось всего несколько месяцев, и Серёже придется реализовать ещё много забавных алгоритмов. Времени все меньше, а если он не успеет, то не защитится, и ему придется восстанавливаться на пятый курс. Опять.
Помогите, пожалуйста, Серёже в нелёгком деле написания диплома, и попробуйте сразиться с этой неприятной подзадачей.
Напомним, что дерево — неориентированный связный граф без циклов. Мостом называется ребро неориентированного графа, при удалении которого количество компонент связности этого графа увеличивается.
Дано дерево YourTree из N (2 ≤ N ≤ 100 000) вершин. Ваша задача — подсчитывать количество мостов в графах, полученных добавлением к дереву YourTree наборов из Ki рёбер.
В первой строке ввода записаны целые числа N и M (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000) — количество вершин в дереве и количество запросов.
Во второй строке находится описание дерева YourTree: последовательность из N - 1 целого числа p2, p3, ..., pN, задающая рёбра (2, p2), (3, p3), ..., (N, pN). Соседние числа разделены пробелами. Гарантируется, что pi < i, а также что эти рёбра образуют дерево.
Далее идут описания M запросов, по одному на строке. Запрос с номером i описывается неотрицательным целым числом Ki и Ki парами чисел от 1 до N — рёбрами, которые добавляются к дереву при построении графа.
Сумма Ki по всем запросам не превосходит 100 000.
Заметим, что в полученных графах допустимы петли и кратные рёбра. Помните, что кратные рёбра не могут являться мостами.
В ответ на каждый запрос выведите одно целое число — количество мостов в графе, полученном добавлением к дереву YourTree заданного набора рёбер.
7 8
1 1 2 2 3 3
1 4 5
3 4 5 6 7 3 2
1 5 6
1 1 1
1 3 6
2 4 3 2 7
1 5 1
3 1 2 1 3 1 6
4
0
2
6
5
2
4
3
| Dynamic Connectivity Training |
|---|
| Закончено |
