Connect

Because of all the travelling around the country for IATI 2022, the tour guide company of Kyusho was once again overwhelmed with questions. The region that his company is responsible for consists of $N$ cities, numbered from $1$ to $N$. Between them, there are $M$ direct roads, numbered from $1$ to $M$, each connecting a pair of different cities. There may be more than one direct road in a given direction between two cities.

The dispatch department often receives questions from bus drivers of this form: "Can you always go from city $A$ to city $B$ and then go back to city $A$ even if one of the roads is closed?"

Kyusho knows that you are an experienced programmer, so he asks you to write a program connect that answers these questions.

The first line contains two positive integers $N$, the number of cities, and $M$, the number of direct roads. Each of the next $M$ lines contains two positive integers $A$ and $B$, meaning there is a direct road from city $A$ to city $B$.

The next line contains the positive integer $Q$, the number of questions. Each of the following $Q$ lines contains two positive integers $A$ and $B$, describing one question about cities $A$ and $B$.

Sometimes there are so many questions that it is better to get the answer for every unordered pair of cities $(A, B)$. When $Q = 0$, the answers are needed for the pairs $(1,1), (1,2), (1,3), \dots, (1,N), (2,2), (2,3), \dots, (2,N), (3,3), \dots, (N,N)$, in that order.

For each question, assign a number as follows.

• $0$: Even without closing one of the roads, there is no route between the two cities in at least one of the two directions.
• $M+1$: No matter which road is closed, there is always a route between the two cities in both directions.
• A number between $1$ and $M$: the number of the road whose closure leaves no route in one of the two directions. If more than one road qualifies, print the lowest-numbered one.

Let the resulting numbers be $s_1, s_2, \dots, s_K$, where $K = Q$ if $Q \neq 0$, and $K = \frac{N \times (N+1)}{2}$ if $Q = 0$. Print on one line the remainder of

$P = s_1 \times B^{K-1} + s_2 \times B^{K-2} + \cdots + s_K \times B^0$

modulo $10^9 + 7$, where $B = 2 \times 10^5$.

• $2 \le N \le 2000$
• $1 \le A, B \le N$
• $1 \le M \le 10^5$
• $0 \le Q \le 10^5$