仙人掌树的同构

首先，先介绍仙人掌树。仙人掌树是一张无向图，但是每个节点最多只会在一个环里面，而且这张图的环全部都是简单环，即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。

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