简单路径(Simple Path)

题目描述

给定一个由 n 个点、n 条边组成的无向连通图，这张图不存在重边，也不存在自环。请问在这张图上，存在多少条简单路径？

所谓简单，是指路径的起点与终点不相同，且路径上的任何点、任何边都不会在路径上重复出现。所谓重边，是指两条不同的边，连接了同一对点。所谓自环，是指一条边，连接了同一个点。

输入格式

第一行：单个正整数表示 n； 第二行到第 n+1 行：每行两个点 u 和 v，表示一条边连接了编号为 u 与 v 的点。图的结点编号为 1 到 n 之间的整数。

输出格式

单个整数：表示简单路径的条数，由于数字可能很大，输出答案模 10⁹+7 的余数。

数据范围

• 对于 30% 的数据，n ≤ 200；
• 对于 50% 的数据，n ≤ 2000；
• 对于 70% 的数据，n ≤ 20000；
• 对于 100% 的数据，3 ≤ n ≤ 200000。

样例输入 #1

3
1 2
2 3
3 1

样例输出 #1

12

样例1说明： 1->2 2->1 1->3 3->1 2->3 3->2 1->2->3 1->3->2 2->1->3 2->3->1 3->1->2 3->2->1

样例输入 #2

6
1 2
2 3
3 1
1 4
1 5
2 6

样例输出 #2

52

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐。

测试点分布