Hafiz Batyrkhan

Задача №1.

Задача F. Yosik - город где сбываются мечты

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Yosik - это город Казахстана где сбываются мечты миллионов. И при этом Yosik - важнейший экономический центр всего мира. Yosik, наряду с Лондоном и Токио, называют одним из трёх основных центров мировой экономики. Ну конечно же, без мэра CMaster город не был бы таким популярным. Он приложил все свои усилия чтобы достичь этого. Но экономическая война между другими странами повлиял негативно на экономику Yosik-a. Мэр хочет улучшить качество некоторых дорог в городе. И в городе существует $n$ районов. Каждый район имеет экономический статус: Высокий или Низкий. И чтобы мэр CMaster принял правильное решение об улучшении дорог во время кризиса в городе он должен узнать сколько пар Высоких важности районов это дорога соединяет. То есть, дорога соединяет два Высоких важности районов $(a, b)$ если и только если все пути между этими двумя районами проходят через эту дорогу. И есть $q$ событии двух видов: 1) Сделать статус района $v$ $(1 <=q v <=q n)$ Высоким если он Низкий, а иначе сделать его Низким. 2) Для дороги $i$ сказать количество пар районов $(a, b)$ с Высоким статусом что дорога $(1 <=q i <=q m)$ лежит на всех путях между этими районами $(a, b)$. И при этом пары $(a, b)$ и $(b, a)$ считаются одинаковыми Город можно представить как связный неориентированный граф с $n$ вершинами и $m$ ребрами. Где вершина это район а ребро это дорога. Каждый район имеет статус экономического важности либо Высокий либо Низкий. Вначале все районы имеют Низкий важность для экономики. Из района может существовать дорога которая соединяет район с собой (петля), но не существует кратные ребра, то есть дороги которые соединяют одинаковую пар вершин.

Формат входного файла

На первой строке даны 3 числа $n$, $m$ и $q$, количество районов, дорог и событии, соответственно. Далее следует $m$ чисел - неориентированные ребра в Yosik-e. В графе не существует две одинаковых ребер, но могут быть петли Потом вам дается запросы в виде $(type, number)$. Если $type = 1$, то это первый тип запросов и $number$ означает номер вершины, $(1 <=q number <=q n)$. А если $type = 2$, то это второй тип запросов и число означает номер ребра в порядке входных данных, $(1 <=q number <=q m)$

Формат выходного файла

Для каждого запроса вида 2, вы должны вывести количество пар город $(a, b)$ которые имеют статус Высокой важности что ребро $i$ лежит на всех путях между этими вершинами $(a, b)$

Система оценки

Данная задача содержит четыре подзадач: 1. $1 <=q n, q <=q 10$. Подзадача оценивается в 10 баллов 2. $1 <=q n, m, q <=q 300$. Подзадача оценивается в 14 баллов 3. $1 <=q n, m, q <=q 2000$. Подзадача оценивается в 22 баллов 4. Город является деревом $1 <=q n, q <=q 10^5, m = n - 1$. Подзадача оценивается в 24 баллов 5. $1 <=q n, m, q <=q 10^5$. Подзадача оценивается в 30 баллов

Пример:

Вход

Ответ

Замечание

Граф из первого теста (перед запросом с номером 5)

Можно заметить что выделенная ребро (ребро с индексом 1) соединяет 2 пары вершин: (1, 2) и (1, 4) Но, еще заметим что ребро (2, 4) не соединяет вершины 2 и 4 так как существует путь (2 -> 3 -> 4). ( Hafiz Batyrkhan )
комментарий/решение(6) олимпиада

Задача №2.