Обязательные вершины
Обязательные вершины
Дан связный неориентированный граф, состоящий из n вершин и m рёбер. В нём выделены две вершины - s и t.
Требуется найти в нём все такие вершины, через которые проходят все пути между s и t. Сами вершины s и tтакже следует включить в ответ.
Входные данные
В первой строке входного файла заданы целые числа n и m (2 ≤ n ≤ 100000, 1 ≤ m ≤ 300000). В каждой из последующих m строк содержится по два числа x_i и y_i - номера вершин, которые соединяет i-ое ребро (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i). Каждая пара вершин соединена не более чем одним ребром. В следующей строке записано число k (1 ≤ k ≤ 100000). далее следует k строк с запросами, каждый из которых состоит из двух чисел s и t (1 ≤ s, t ≤ n,s ≠ t).
Выходные данные
Для каждого запроса необходимо вывести три числа - минимальный номер, максимальный номер и сумму номеров всех вершин, входящих в ответ на запрос.
Пример
4 3 1 2 2 3 3 4 2 1 4 2 3
1 4 10 2 3 5