Мосты через Чуй
Вдоль реки Чуй 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.
Подсказка
Сожмите компоненты рёберной двусвязности: получится дерево, рёбра которого — мосты. Ответ — расстояние в этом дереве.
Комментарии