Geodetic Set in Graphs

Given an undirected connected graph (G) with no self-loops and at most one edge between any two vertices, we define the shortest path between two vertices (v) and (u) as a path with the minimum number of edges between them. All vertices belonging to any shortest path from (v) to (u) are called the geodetic vertices, denoted as (I(v,u)).

For example, in the graph below, we have: [ I(2,5) = {2,3,4,5}, \quad I(1,5) = {1,3,5}, \quad I(2,4) = {2,4} ]

You are given graph (G) and several queries, each consisting of a pair of vertices (v) and (u). Your task is to compute the geodetic set (I(v,u)), i.e. the union of all vertices on any shortest path between (v) and (u).

Note: A vertex (x) belongs to (I(v,u)) if and only if: [ \textit{dist}(v, x) + \textit{dist}(x, u) = \textit{dist}(v, u) ] where (\textit{dist}(a, b)) is the number of edges in the shortest path from (a) to (b).

inputFormat

The first line contains two integers n and m, the number of vertices and edges respectively.

The next m lines each contain two integers a and b, representing an undirected edge between vertices a and b.

The following line contains an integer q, the number of queries.

Each of the next q lines contains two integers v and u, for which you need to compute the geodetic set \(I(v,u)\).

outputFormat

For each query, output a single line with the vertices in \(I(v,u)\), sorted in increasing order and separated by spaces.

sample

5 5
1 3
2 3
3 4
4 5
2 5
3
2 5
1 5
2 4

2 3 4 5
1 3 5
2 4