CF1425B Blue and Red of Our Faculty!

这是我们学院第 34 个周年纪念日！为了庆祝这个伟大的时刻，印度尼西亚大学计算机科学学院（Fasilkom）举办了 CPC —— 彩色人行道比赛。CPC 的核心玩法是两名选手用蓝色和红色为 Fasilkom 的预定路线上色。有 $N$ 个检查点和 $M$ 条无向的预定路线。第 $i$ 条路线连接检查点 $U_i$ 和 $V_i$，其中 $1 \le i \le M$。保证任意一对检查点都可以通过一条或多条路线连通。 CPC 的规则如下： - 每轮有两名选手参与。一名选手扮演蓝方，另一名选手扮演红方。为简便起见，称这两名选手为 $Blue$ 和 $Red$。 - $Blue$ 走过的每一条路线都会被涂成蓝色，$Red$ 走过的每一条路线都会被涂成红色。两名选手都从编号为 $1$ 的检查点出发。初始时，所有路线都是灰色的。 - 每一阶段，两名选手从当前所在的检查点出发，各自选择一条不同的灰色路线，并同时沿着该路线移动到另一端的检查点。 - 当 $Blue$ 或 $Red$ 无法继续移动时（即没有两条不同的灰色路线可供选择），游戏结束。 Chaneka 有兴趣参加比赛，但她不想浪费太多精力。因此，她只关心每轮结束后路线的最终涂色情况有多少种。事实证明，计算这个数量也很耗费精力，于是 Chaneka 请你帮她解决这个问题！ 如果存在一条路线 $U$ 在两种配置中的颜色不同，则认为这两种最终配置是不同的。

第一行包含两个整数 $N$ 和 $M$。$N$ $(2 \le N \le 2 \cdot 10^3)$ 表示检查点的数量，$M$ $(1 \le M \le 2 \cdot N)$ 表示路线的数量。保证除了检查点 $1$ 以外，每个检查点恰好有两条路线与之相连。 接下来的 $M$ 行，每行包含两个整数 $U_i$ 和 $V_i$ $(1 \le U_i, V_i \le N, U_i \ne V_i)$，表示第 $i$ 条路线连接的两个检查点。 保证任意一对检查点都可以通过一条或多条路线直接或间接连通。

输出一个整数，表示每轮 CPC 结束后路线的最终配置数量，对 $10^9 + 7$ 取模。

下图列出了示例的所有可能最终配置：  蓝色数字表示 $Blue$ 的移动顺序，红色数字表示 $Red$ 的移动顺序。 由 ChatGPT 4.1 翻译