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

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

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

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

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

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

На первой строке даны 3 числа nn, mm и qq, количество районов, дорог и событии, соответственно.

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

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

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

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

Для каждого запроса вида 2, вы должны вывести количество пар город (a,b)(a, b) которые имеют статус Высокой важности что ребро ii лежит на всех путях между этими вершинами (a,b)(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