| ABBYY Cup 2.0 - Hard |
|---|
| Закончено |
В ABBYY живет замечательный Умный Бобер. На этот раз он занялся изучением истории. Когда он читал про Римскую империю, его заинтересовала жизнь торговцев.
Римская империя состояла из n городов, пронумерованных от 1 до n. В ней также существовало m двунаправленныx дорог, пронумерованных от 1 до m. Каждая дорога связывала между собой два различных города. Любые два города были соединены не более чем одной дорогой.
Будем говорить, что между городами c1 и c2 существует путь, если существует конечная последовательность городов t1, t2, ..., tp (p ≥ 1) такая, что:
- t1 = c1
- tp = c2
- для любого i (1 ≤ i < p) города ti и ti + 1 связаны дорогой
Известно, что в Римской империи между любыми двумя городами существовал путь.
В империи жили k торговцев, пронумерованных от 1 до k. Для каждого из них известна пара чисел si и li, где si — номер города, в котором расположен склад данного торговца, а li — номер города, в котором расположена его торговая лавка. Лавка и склад могли находиться в разных городах, поэтому торговцам приходилось доставлять товар со склада до торговой лавки.
Назовем дорогу важной для торговца, если ее разрушение грозит торговцу разорением, то есть если без этой дороги не существует пути от его склада до его лавки. Торговцы в Римской империи очень жадные, поэтому каждый торговец платит налог (1 динарий) только за важные для него дороги. Другими словами, каждый торговец платит налог di динариев, где di (di ≥ 0) — количество важных для данного торговца дорог.
В империи настал день сбора налогов. Умный Бобер из ABBYY по природе своей очень любопытен, поэтому он решил посчитать, сколько динариев заплатил каждый торговец. И в этом ему нужна Ваша помощь.
В первой строке входных данных записано два целых числа n и m, разделенных пробелом. Число n — это количество городов, а m — количество дорог в империи.
Следующие m строк содержат пары целых чисел ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), разделенных пробелом, — номера городов, соединенных i-ой дорогой. Гарантируется, что любые два города соединены не более чем одной дорогой и что в Римской империи между любыми двумя городами существует путь.
Следующая строка содержит целое число k — количество торговцев в империи.
Следующие k строк содержат пары целых чисел si, li (1 ≤ si, li ≤ n), разделенных пробелом, — число si обозначает номер города, в котором расположен склад i-го торговца, li — номер города, в котором расположена лавка i-го торговца.
Ограничения на входные данные для получения 20 баллов:
- 1 ≤ n ≤ 200
- 1 ≤ m ≤ 200
- 1 ≤ k ≤ 200
Ограничения на входные данные для получения 50 баллов:
- 1 ≤ n ≤ 2000
- 1 ≤ m ≤ 2000
- 1 ≤ k ≤ 2000
Ограничения на входные данные для получения 100 баллов:
- 1 ≤ n ≤ 105
- 1 ≤ m ≤ 105
- 1 ≤ k ≤ 105
Выведите ровно k строк, в i-ой из которых будет записано целое число di — число динариев, которое заплатил торговец с номером i.
7 8
1 2
2 3
3 4
4 5
5 6
5 7
3 5
4 7
4
1 5
2 4
2 6
4 7
2
1
2
0
Данный пример проиллюстрирован на рисунке.
Распишем результат для первого торговца. Склад торговца находится в городе 1, а лавка в городе 5. Заметим, что при разрушении любой из дорог (1, 2) или (2, 3) путь между городами 1 и 5 пропадает. При разрушении любой другой дороги путь сохранится. Поэтому для данного торговца ответ 2.
