CF231E.Cactus

A connected undirected graph is called a vertex cactus, if each vertex of this graph belongs to at most one simple cycle.

A simple cycle in a undirected graph is a sequence of distinct vertices _v_1, _v_2, ..., v__t (t > 2), such that for any i (1 ≤ i < t) exists an edge between vertices v__i and v__i + 1, and also exists an edge between vertices _v_1 and v__t.

A simple path in a undirected graph is a sequence of not necessarily distinct vertices _v_1, _v_2, ..., v__t (t > 0), such that for any i (1 ≤ i < t) exists an edge between vertices v__i and v__i + 1 and furthermore each edge occurs no more than once. We'll say that a simple path _v_1, _v_2, ..., v__t starts at vertex _v_1 and ends at vertex v__t.

You've got a graph consisting of n vertices and m edges, that is a vertex cactus. Also, you've got a list of k pairs of interesting vertices x__i, y__i, for which you want to know the following information — the number of distinct simple paths that start at vertex x__i and end at vertex y__i. We will consider two simple paths distinct if the sets of edges of the paths are distinct.

For each pair of interesting vertices count the number of distinct simple paths between them. As this number can be rather large, you should calculate it modulo 1000000007 (109 + 7).

一个连通的无向图被称为点仙人掌图（vertex cactus），当且仅当该图中每个顶点至多属于一个简单环。

无向图中的一个简单环（simple cycle） 是一个由互不相同的顶点 $v_1,\,v_2,\,\dots,\,v_t$（其中 $t > 2$）构成的序列，使得对任意 $i$（$1 \le i < t$），顶点 $v_i$ 与 $v_{i+1}$ 之间存在一条边，且顶点 $v_1$ 与 $v_t$ 之间也存在一条边。

无向图中的一个简单路径（simple path） 是一个顶点序列 $v_1,\,v_2,\,\dots,\,v_t$（其中 $t > 0$），这些顶点不一定互不相同，满足：对任意 $i$（$1 \le i < t$），顶点 $v_i$ 与 $v_{i+1}$ 之间存在一条边，且图中每条边在该路径中至多出现一次。我们称简单路径 $v_1,\,v_2,\,\dots,\,v_t$ 起始于顶点 $v_1$、终止于顶点 $v_t$。

现给定一个由 $n$ 个顶点和 $m$ 条边构成的图，它是一个点仙人掌图；同时还给定一个包含 $k$ 对“感兴趣顶点” $(x_i,\,y_i)$ 的列表。对于每一对 $(x_i,\,y_i)$，你需要计算：起始于顶点 $x_i$、终止于顶点 $y_i$ 的不同简单路径的数量。若两条简单路径所含的边集不同，则认为它们是不同的路径。

对每一对感兴趣顶点，计算它们之间不同简单路径的数量。由于该数量可能非常大，请将结果对 $1000000007$（即 $10^9 + 7$）取模。

The first line contains two space-separated integers n, m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105) — the number of vertices and edges in the graph, correspondingly. Next m lines contain the description of the edges: the i-th line contains two space-separated integers a__i, b__i (1 ≤ a__i, b__i ≤ n) — the indexes of the vertices connected by the i-th edge.

The next line contains a single integer k (1 ≤ k ≤ 105) — the number of pairs of interesting vertices. Next k lines contain the list of pairs of interesting vertices: the i-th line contains two space-separated numbers x__i, y__i (1 ≤ x__i, y__i ≤ n; x__i ≠ y__i) — the indexes of interesting vertices in the i-th pair.

It is guaranteed that the given graph is a vertex cactus. It is guaranteed that the graph contains no loops or multiple edges. Consider the graph vertices are numbered from 1 to n.

第一行包含两个以空格分隔的整数 $n$、$m$（$2 \leq n \leq 10^5$；$1 \leq m \leq 10^5$），分别表示图中的顶点数和边数。接下来的 $m$ 行描述各条边：第 $i$ 行包含两个以空格分隔的整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$），表示第 $i$ 条边所连接的两个顶点的编号。

下一行包含一个整数 $k$（$1 \leq k \leq 10^5$），表示“感兴趣顶点对”的数量。接下来的 $k$ 行列出所有感兴趣顶点对：第 $i$ 行包含两个以空格分隔的数 $x_i$、$y_i$（$1 \leq x_i, y_i \leq n$；$x_i \neq y_i$），表示第 $i$ 对中两个感兴趣顶点的编号。

保证所给图是一个顶点仙人掌图（vertex cactus）。保证图中不含自环或重边。图中顶点编号为 $1$ 到 $n$。

Print k lines: in the i-th line print a single integer — the number of distinct simple ways, starting at x__i and ending at y__i, modulo 1000000007 (109 + 7).

输出 k 行：第 i 行输出一个整数——从 x__i 出发、到 y__i 结束的不同的简单路径的数量，对 1000000007（即 $10^9 + 7$）取模。