#P3899. 仙人掌树的同构

    ID: 3101 传统题 1000ms 256MiB 尝试: 167 已通过: 36 难度: 8 上传者: 标签>CF2500提高+/省选-仙人掌图圆方树深度优先搜索AHU 算法树形 DP排列数计算对称性分析轨道—稳定子定理

仙人掌树的同构

题目描述

首先,先介绍仙人掌树。仙人掌树是一张无向图,但是每个节点最多只会在一个环里面,而且这张图的环全部都是简单环,即 A→B→C→AA\to B\to C\to A 这种。

比如下图就是一颗仙人掌树。

好的,知道了仙人掌树之后,我们现在要计算一个东西。

我们现在已经知道了一个 nn 个节点的仙人掌树,称作为原图。接下来,我们要用 1…n1\dots n 的一个排列 a1…ana_1\dots a_n 去变换这棵树,具体的,如果原图中有一条边 i↔ji \leftrightarrow j,那么变换出来的图中必须有一条 ai↔aja_i \leftrightarrow a_j 的边。同样的,如果变换出来的图中有一条 ai↔aja_i \leftrightarrow a_j 的边,那么原图中必有一条 i↔ji\leftrightarrow j 的边。(简单而言就是点重新编号)

小 A 为了超脱宇宙的束缚,必须要知道,有多少种排列,可以使得变换出来的新图和原图是一模一样的,具体的,原图中如果存在一条 i↔ji \leftrightarrow j 的边,新图也存在一条 i↔ji\leftrightarrow j 的边,新图中存在一条 i↔ji \leftrightarrow j 的边,原图中也存在 i↔ji \leftrightarrow j 的边。

方案数目答案  mod 109+3\bmod 10^9+3。

输入格式

第一行有两个正整数,nn 和 mm,节点个数和边的个数。

接下来 mm 行,每行有两个正整数 u,vu,v,表示一条原图的无向边。

输出格式

一行一个正整数,表示方案数目。

5 5
1 2
2 3
3 4
4 5
1 5
10

样例说明

所有的答案包括 $(i,(i+1) \bmod 5 + 1,(i+2) \bmod 5 + 1,(i+3) \bmod 5 + 1,(i+4) \bmod 5 + 1)$ 和 $(i,(i+4) \bmod 5 + 1,(i+3) \bmod 5 + 1,(i+2) \bmod 5 + 1,(i+1) \bmod 5 + 1)$ 这两种类型。每种类型的 ii 可以是 1,2,3,4,51,2,3,4,5,所以答案是 2×5=102\times 5=10。

数据规模与约定

对于 100%100\% 的数据,1≤n≤1031\le n\le 10^3。

数据保证没有重边。

题目来源

By 佚名提供