#5768. 「CEOI2026」DFS

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 CEOI 2026 Day1 T2「DFS」

你可能已经熟悉用于遍历图的著名深度优先搜索（DFS）算法。在本题中，我们仅考虑顶点编号为 $0, 1, \dots, n-1$ 的连通无向简单图（即不含自环和重边），DFS 算法将按如下方式输出深度和顶点：

DFS(d, v):
    输出 d/v
    将顶点 v 标记为已访问
    W = v 的所有邻居构成的列表，按顶点编号升序排列
    对于 W 中的每个顶点 w:
        若顶点 w 尚未被访问:
            DFS(d + 1, w)

请编写一个程序，计算对于调用 $\operatorname{DFS}(0, n-1)$ 能够产生与输入给出的输出结果相同的所有不同图的数量。例如，对于如下输出：

0/2
1/0
2/1

可通过对以下两张连通无向简单 $3$ 顶点图中的任意一张调用 $\operatorname{DFS}(0, 2)$ 得到：

输入格式

输入是在某张未知的 $n$ 个顶点的连通无向简单图上调用 $\operatorname{DFS}(0, n-1)$ 的输出结果。因此输入由 $n$ 行组成，格式为 d/v，其中第一行为 0/n-1。

输出格式

输出满足要求的不同图的数量。由于该数量可能非常大，请将结果对 $1000000007$ 取模后输出。

样例

输入

0/2
1/0
2/1

输出

2

在该样例中，满足调用 $\operatorname{DFS}(0, 2)$ 后能产生此输出结果的连通无向简单 $3$ 顶点图共有 $2$ 张。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 2 \cdot 10^5$

详细子任务附加限制及分值如下表所示。