P13765 [CERC 2021] Cactus cutting

Malnar 先生已经放弃了他对树的执着，转而对仙人掌（cactus）产生了兴趣！形式上，仙人掌是一种连通图，其中每条边至多属于一个环。一个环被定义为一系列超过一条的不同边，其中每两条相邻的边有一个公共端点，并且首尾两条边也有一个公共端点。 不幸的是，Malnar 先生买的仙人掌太大了，他想把它切割成互不相交的“棍子”。一根棍子被定义为一对有公共端点的边。Malnar 先生是个很讲究的人，他想知道有多少种不同的方法可以把他的仙人掌切割成棍子。

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

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

### 输入范围 - $1 \leq N, M \leq 100\,000$ - $1 \leq A_i, B_i \leq N$ 由 ChatGPT 4.1 翻译