Mandatory vertices#3678
A connected undirected graph is provided, consisting of vertices and edges. Within this graph, two specific vertices, and , are highlighted.
Your task is to identify all vertices through which every path between and must pass. The vertices and themselves should be included in the result.
The first line of the input contains two integers, and (2 \le n \le 100000, 1 \le m \le 300000). Each of the next lines contains two integers x_i and y_i, representing the vertices connected by the -th edge (1 \le x_i, y_i \le n, x_i \neq y_i). No pair of vertices is connected by more than one edge. The following line contains the integer (1 \le k \le 100000). After this, there are lines of queries, each containing two integers and (1 \le s, t \le n, s \neq t).
For each query, output three numbers: the smallest number, the largest number, and the sum of the numbers of all vertices that are part of the solution for that query.
Example 1