Unavoidable Houses

In Yaegor village, there are \( n \) houses and initially no roads. As the village develops, bidirectional roads are gradually constructed between the houses. Life is peaceful until a mysterious collapse phenomenon occurs and strange creatures (崩坏兽) begin to attack some houses. To counter this menace, Sakura, a renowned exorcist, accepts assignments where she must exorcise the beasts along the route from one house to another.

Sakura can only travel along existing roads. Since there might be many paths between the two houses, she smartly chooses to exorcise only those houses that appear on every possible path between the two given houses; these are called unavoidable houses. Note that the starting and ending houses are not considered unavoidable even if they appear in every path.

Given the layout of the village and multiple exorcism assignments, determine for each assignment the set of unavoidable houses. If no such house exists, output -1.

inputFormat

The first line contains two integers \( n \) and \( m \) (\(1 \leq n \leq N\), \(0 \leq m \leq M\)) representing the number of houses and roads respectively.

Each of the next \( m \) lines contains two integers \( u \) and \( v \) (\(1 \leq u, v \leq n, u \neq v\)) denoting a bidirectional road between house \( u \) and house \( v \).

The next line contains an integer \( q \), the number of queries.

Each of the following \( q \) lines contains two integers \( u \) and \( v \) (\(1 \leq u, v \leq n, u \neq v\)) representing an exorcism assignment from house \( u \) to house \( v \).

outputFormat

For each query, output on a separate line the unavoidable houses (in increasing order) that lie on every path from the starting house to the destination house. If there is no unavoidable house, output -1.

sample

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

2 3 4
3