一个连通的无向图被称为顶点仙人掌,如果该图的每个顶点最多属于一个简单循环。
无向图中的简单循环是一系列不同的顶点 v1, v2, ..., vt (t > 2),因此对于任何 i (1 ≤ i < t),在顶点 vi 和 vi + 1 之间存在一条边,并且在顶点 v1 和 vt 之间也存在一条边。
无向图中的简单路径是一系列不一定不同的顶点 v1, v2, ..., vt (t > 0),这样对于任何 i (1 ≤ i < t),在顶点 vi 和 vi + 1 之间存在一条边,而且每条边最多出现一次。我们会说简单路径 v1, v2, ..., vt 从顶点 v1 开始,到顶点 vt 结束。
你有一个由 n 个顶点和 m 个边组成的图,这是一个顶点仙人掌。此外,您还获得了 k 对有趣的顶点 xi、yi 的列表,您想了解这些顶点的以下信息 - 从顶点 xi 开始到顶点 yi 结束的不同简单路径的数量。如果路径的边集不同,我们将认为两条简单路径是不同的。
对于每对有趣的顶点,计算它们之间不同的简单路径的数量。由于这个数字可能相当大,因此您应该以 1000000007 (109 + 7) 为模来计算它。
输入
第一行包含两个空格分隔的整数 n, m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105) — 相应地,图中的顶点和边的数量。接下来的 m 行包含边的描述:第 i 行包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n) — 第 i 条边连接的顶点的索引。
下一行包含一个整数 k (1 ≤ k ≤ 105) — 感兴趣的顶点对的数量。接下来的 k 行包含有趣顶点对的列表:第 i 行包含两个以空格分隔的数字 xi, yi (1 ≤ xi, yi ≤ n; xi ≠ yi) — 第 i 对中有趣顶点的索引。
保证给定的图是顶点仙人掌。保证图不包含循环或多重边。考虑图的顶点编号为 1 到 n。
输出
打印 k 行:在第 i 行中打印一个整数 — 不同简单方法的数量,从 xi 开始,到 yi 结束,模 1000000007 (109 + 7)。
示例
输入 #1
10 11 1 2 2 3 3 4 1 4 3 5 5 6 8 6 8 7 7 6 7 9 9 10 6 1 2 3 5 6 9 9 2 9 3 9 10
输出 #1
2 2 2 4 4 1