Мосты через Чуй


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Вдоль реки Чуй n сёл соединены m дорогами (между двумя сёлами может быть несколько дорог). Из любого села можно доехать до любого другого. Некоторые дороги — «мосты»: если такую дорогу перекрыть, найдутся сёла, между которыми больше нельзя проехать.

Рисунок

Весной реки разливаются. Для каждого из q вопросов u v определите, сколько существует дорог, без которых из u нельзя доехать в v (то есть таких, что любой путь из u в v проходит по ним).

Входные данные

В первой строке — n, m, q (1 ≤ n ≤ 2 · 10⁵, n − 1 ≤ m ≤ 2 · 10⁵ + 50 000, 1 ≤ q ≤ 2 · 10⁵). В каждой из следующих m строк — два различных числа a b: дорога между сёлами. В каждой из следующих q строк — два числа u v.

Выходные данные

Для каждого вопроса выведите количество таких дорог.

Пример 1

Вход:

5 6 3
1 2
2 3
3 1
3 4
4 5
5 4
1 5
4 5
2 3

Выход:

1
0
0

Пояснение

Дороги 1–2, 2–3, 3–1 образуют кольцо, дорога 3–4 — мост, сёла 4 и 5 соединены двумя дорогами, поэтому ни одна из них не мост. Из 1 в 5 обязательно проезжать только мост 3–4.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 30.

Подсказка

Сожмите компоненты рёберной двусвязности: получится дерево, рёбра которого — мосты. Ответ — расстояние в этом дереве.


Комментарии

Еще нет ни одного комментария.