BZPRO
#3899. 仙人掌树的同构
内存限制：512 MiB
时间限制：1 Sec
提交
提交记录
讨论
题目描述
首先，先介绍仙人掌树。仙人掌树是一张无向图，但是每个节点最多只会在一个环里面，而且这张图的环全部都是简单环，即A->B->C->A这种。
比如下图就是一颗仙人掌树。
好的，知道了仙人掌树之后，我们现在要计算一个东西。
我们现在已经知道了一个N个节点的仙人掌树，称作为原图。接下来，我们要用1-N的一个排列A[1]-A[N]去变换这棵树，具体的，如果原图中有一条边i-j，那么变换出来的图中必须有一条A[i]-A[j]的边。同样的，如果变换出来的图中有一条A[i]-A[j]的边，那么原图中必有一条i-j的边。（简单而言就是点重新编号）
小A为了超脱宇宙的束缚，必须要知道，有多少种排列，可以使得变换出来的新图和原图是一模一样的，具体的，原图中如果存在一条i-j的边，新图也存在一条i-j的边，新图中存在一条i-j的边，原图中也存在i-j的边。
方案数目答案mod 1000000003。
输入格式
第一行有两个正整数，N和M，节点个数和边的个数。
接下来M行，每行有2个正整数S，T，表示一条原图的无向边。数据保证没有重边。
输出格式
一行一个正整数表示方案书目。
样例
样例输入
5 5
1 2
2 3
3 4
4 5
1 5
样例输出
10
数据范围与提示
所有的答案包括(i,(i+1) % 5 + 1,(i+2) % 5 + 1,(i+3) % 5 + 1,(i+4) % 5 + 1)和(i,(i+4) % 5 + 1,(i+3) % 5 + 1,(i+2) % 5 + 1,(i+1) % 5 + 1)这两种类型。每种类型的i可以是12345，所以答案是2*5=10。
N<=1000
BZPRO