题目描述

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

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

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

我们现在已经知道了一个 $n$ 个节点的仙人掌树，称作为原图。接下来，我们要用 $1\dots n$ 的一个排列 $a_1\dots a_n$ 去变换这棵树，具体的，如果原图中有一条边 $i \leftrightarrow j$，那么变换出来的图中必须有一条 $a_i \leftrightarrow a_j$ 的边。同样的，如果变换出来的图中有一条 $a_i \leftrightarrow a_j$ 的边，那么原图中必有一条 $i\leftrightarrow j$ 的边。（简单而言就是点重新编号）

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

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

输入格式

第一行有两个正整数，$n$ 和 $m$，节点个数和边的个数。

接下来 $m$ 行，每行有两个正整数 $u,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)$ 这两种类型。每种类型的 $i$ 可以是 $1,2,3,4,5$，所以答案是 $2\times 5=10$。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^3$。

数据保证没有重边。

题目来源

By 佚名提供