Областная олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

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

Yosik - это город Казахстана где сбываются мечты миллионов. И при этом Yosik - важнейший экономический центр всего мира. Yosik, наряду с Лондоном и Токио, называют одним из трёх основных центров мировой экономики.

Ну конечно же, без мэра

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

На первой строке даны 3 числа $n$, $m$ и $q$, количество районов, дорог и событии, соответственно.

Далее следует $m$ чисел - неориентированные ребра в Yosik-e.

В графе не существует две одинаковых ребер, но могут быть петли

Потом вам дается запросы в виде $(type, number)$. Если $type = 1$, то это первый тип запросов и $number$ означает номер вершины, $(1 <=q number <=q n)$. А если $type = 2$, то это второй тип запросов и число означает номер ребра в

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

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

Примеры

Вход

9 10 10
1 2
3 2
4 3
2 4
3 5
8 5
9 8
5 6
5 7
7 6
1 2
1 1
1 4
2 5
2 1
1 9
1 7
1 5
2 5
2 2

Выход

0
2
9
0