Mandatory vertices
A connected undirected graph is provided, consisting of n vertices and m edges. Within this graph, two specific vertices, s and t, are highlighted.
Your task is to identify all vertices through which every path between s and t must pass. The vertices s and t themselves should be included in the result.
Input
The first line of the input contains two integers, n and m (2 ≤ n ≤ 100000, 1 ≤ m ≤ 300000). Each of the next m lines contains two integers x_i and y_i, representing the vertices connected by the i-th edge (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i). No pair of vertices is connected by more than one edge. The following line contains the integer k (1 ≤ k ≤ 100000). After this, there are k lines of queries, each containing two integers s and t (1 ≤ s, t ≤ n, s ≠ t).
Output
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.