Description

Malnar 先生已经放弃了他对树的执着，转而对仙人掌（cactus）产生了兴趣！形式上，仙人掌是一种连通图，其中每条边至多属于一个环。一个环被定义为一系列超过一条的不同边，其中每两条相邻的边有一个公共端点，并且首尾两条边也有一个公共端点。

不幸的是，Malnar 先生买的仙人掌太大了，他想把它切割成互不相交的“棍子”。一根棍子被定义为一对有公共端点的边。Malnar 先生是个很讲究的人，他想知道有多少种不同的方法可以把他的仙人掌切割成棍子。

Input Format

第一行包含两个整数 $N$ 和 $M$，分别表示顶点数和边数。接下来的 $M$ 行，每行包含两个不同的整数 $A_{i}$ 和 $B_{i}$，表示在顶点 $A_{i}$ 和 $B_{i}$ 之间有一条边。每条边只会出现一次。

Output Format

计算 Malnar 先生将他的仙人掌切割成棍子的不同方法数。由于答案可能很大，请输出结果对 $10^6 + 3$ 取模后的值。

10 12
1 6
2 5
7 2
8 9
8 1
2 6
4 3
4 10
3 10
3 9
1 3
5 7

8

Hint

输入范围

• $1 \leq N, M \leq 100\,000$
• $1 \leq A_i, B_i \leq N$

由 ChatGPT 4.1 翻译