[Usaco2012Jan]Bovine Alliance

Bessie 和附近农场的伙伴们决定修建小径，将各个农场连接起来，以组成对抗农场主的联盟。

共有 $N$ 个农场。每个农场原本都需要负责修建恰好 $1$ 条连接到其他农场的小径，因此计划修建 $N$ 条小径。然而几个月后，实际只建成了其中的 $M$ 条。现在，各个农场对这些小径究竟是由谁修建的产生了争议。

对于每条已经建成的小径，需要将它归属于其连接的两个农场之一。例如，若一条小径连接农场 $3$ 和农场 $4$ ，则它可能由农场 $3$ 修建，也可能由农场 $4$ 修建。由于每个农场至多负责修建 $1$ 条小径，因此不同的小径不能归属于同一个农场。

请计算所有合法归属方案的数量。若两个方案中至少有一条小径归属的农场不同，则认为它们是不同的方案。答案对 $10^9+7$ 取模。

等价地，需要将图中的点和边分组：每条边必须与其两个端点之一分在同一组，每个点至多与一条边同组，也可以单独成组。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$ ，分别表示农场数量和已经建成的小径数量。

接下来 $M$ 行，第 $i$ 行包含两个以空格分隔的整数 $u_i$ 和 $v_i$ ，表示第 $i$ 条小径连接农场 $u_i$ 和农场 $v_i$ 。

同一对农场之间可能存在多条小径。

输出一个整数，表示合法归属方案的数量对 $10^9+7$ 取模后的结果。

如果不存在合法方案，则输出 $0$ 。

按照输入顺序，用一个四元组表示每条小径分别由哪个农场修建，则共有以下 $6$ 种合法方案：

$(2,3,4,5),\ (2,3,5,4),\ (1,3,4,5),\ (1,3,5,4),\ (1,2,4,5),\ (1,2,5,4)。$

本题为 USACO 2012 年 1 月试题「Bovine Alliance」，题面与测试数据整理自 BZOJ 2582。