eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Обязательные вершины

Обязательные вершины

Лимит времени 4 секунды
Лимит использования памяти 256 MiB

Дан связный неориентированный граф, состоящий из n вершин и m рёбер. В нём выделены две вершины - s и t.

Требуется найти в нём все такие вершины, через которые проходят все пути между s и t. Сами вершины s и tтакже следует включить в ответ.

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

В первой строке входного файла заданы целые числа n и m (2n100000, 1m300000). В каждой из последующих m строк содержится по два числа x_i и y_i - номера вершин, которые соединяет i-ое ребро (1x_i, y_in, x_iy_i). Каждая пара вершин соединена не более чем одним ребром. В следующей строке записано число k (1k100000). далее следует k строк с запросами, каждый из которых состоит из двух чисел s и t (1s, tn,s t).

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

Для каждого запроса необходимо вывести три числа - минимальный номер, максимальный номер и сумму номеров всех вершин, входящих в ответ на запрос.

Пример

Входные данные #1
4 3
1 2
2 3
3 4
2
1 4
2 3
Выходные данные #1
1 4 10
2 3 5
Источник III Международная Летняя школа программирования 2012 г. Севастополь