CF231E Cactus

一个无向连通图被称为“点仙人掌”，如果该图的每个顶点至多属于一个简单环。 在无向图中，一个简单环是指由一系列互不相同的顶点 $v_{1},v_{2},...,v_{t}$（$t>2$）组成的序列，满足对于任意 $i$（$1 \le i < t$），存在一条边连接 $v_{i}$ 和 $v_{i+1}$，同时还存在一条边连接 $v_{1}$ 和 $v_{t}$。 无向图中的一条简单路径是指由不一定不同的顶点 $v_{1},v_{2},...,v_{t}$（$t>0$）组成的序列，满足对于任意 $i$（$1 \le i < t$），存在一条边连接 $v_{i}$ 和 $v_{i+1}$，并且每条边在路径中至多出现一次。我们称简单路径 $v_{1},v_{2},...,v_{t}$ 是从顶点 $v_{1}$ 到顶点 $v_{t}$ 的路径。 现在给定一个含有 $n$ 个顶点和 $m$ 条边的图，该图是一个点仙人掌。同时，给定 $k$ 对感兴趣的顶点对 $(x_{i},y_{i})$，请你回答：从 $x_{i}$ 出发到 $y_{i}$ 结束的不同简单路径共有多少条。我们认为两条简单路径不同，当且仅当它们经过的边集合不同。 对于每对给定的感兴趣顶点，请计算其之间不同的简单路径数。因为答案可能很大，请输出对 $1000000007$（$10^{9} + 7$）取模的结果。

第一行包含两个用空格分隔的整数 $n, m$（$2 \le n \le 10^{5}$；$1 \le m \le 10^{5}$）——图中的顶点数和边数。 接下来 $m$ 行，每行包含两个用空格分隔的整数 $a_{i}, b_{i}$（$1 \le a_{i}, b_{i} \le n$）——第 $i$ 条边连接的两个顶点编号。 接下来一行包含一个整数 $k$（$1 \le k \le 10^{5}$）——感兴趣的顶点对的数量。 接下来的 $k$ 行，每行包含两个用空格分隔的整数 $x_{i}$, $y_{i}$（$1 \le x_{i}, y_{i} \le n$，$x_{i} \ne y_{i}$）——第 $i$ 个感兴趣的顶点对。 保证给定的图是一个点仙人掌，没有自环或重边。顶点编号从 $1$ 到 $n$。

输出 $k$ 行，第 $i$ 行输出一个整数，表示从 $x_{i}$ 到 $y_{i}$ 的不同简单路径数，对 $1000000007$ 取模。

由 ChatGPT 5 翻译