← 返回题目列表

AtCoder · icpc2013autumn_d

D. 永恒-一-

中文机器翻译题面 查看原题

问题陈述

《天长地久-一-》是今年推出的一款获奖网络游戏。该游戏因其可扮演的大量角色而迅速闻名。

在这个游戏中,角色的特点是 属性。该游戏中有$N$个属性,编号为$1$到$N$。每个属性采用两种状态之一, 光 or 黑暗。这意味着这个游戏中有$2^N$种角色。

你可以通过换工作来改变你的性格。尽管这是改变角色属性的唯一方法,但您可以根据需要多次更换职业。

换工作的规则有点复杂。当且仅当存在两个属性 $a$ 和 $b$ 且满足以下四个条件时,才可以将字符从 $A$ 更改为 $B$:

  • 角色$A$的属性$a$的状态是 光.

  • 角色$B$的属性$b$的状态是 光.

  • 不存在属性 $c$ 使得字符 $A$ 和 $B$ 都具有 光 属性 $c$ 的状态。

  • 一对属性 $(a, b)$ 是 兼容.

这里,我们说一对属性 $(a, b)$ 是 兼容 如果存在满足以下三个条件的属性序列 $c_1, c_2, \ldots, c_n$:

  • $c_1 = a$。

  • $c_n = b$。

  • $(c_i, c_{i+1})$ 或 $(c_{i+1}, c_i)$ 是所有 $i = 1, 2, \ldots, n-1$ 的特殊对。您将获得特殊对的列表。

既然你热情地喜欢这个游戏,你就会尝试与所有角色一起玩游戏(这真的很疯狂)。然而,您立即注意到,通过该游戏的转职规则,可以将一个角色更改为一组有限的角色。我们说字符 $A$ 和 $B$ 是 本质上不同 如果您无法通过重复作业更改将字符 $A$ 更改为字符 $B$。

那么,自然会出现以下问题;有多少个本质上不同的角色? 由于输出可能非常大,因此您应该以 $1{,}000{,}000{,}007$ 为模来计算答案。


输入

输入是一系列数据集。 数据集数量不超过 $50$,输入总大小不超过 $5$ MB。

每个数据集的格式如下。

$N$ $M$
$a_1$ $b_1$
:
:
$a_M$ $b_M$

每个数据集的第一行包含两个整数 $N$ 和 $M$($1 \le N \le 10^5$ 和 $0 \le M \le 10^5$)。 然后是 $M$ 行。 第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \lt b_i \le N$),表示第 $i$ 个特殊对。 输入以两个零终止。

如果$i \ne j$,则保证$(a_i, b_i) \ne (a_j, b_j)$。

输出

对于每个数据集,输出本质上不同的字符数以 $1{,}000{,}000{,}007$ 为模。


示例输入

3 2
1 2
2 3
5 0
100000 0
0 0

样本输入的输出

3
32
607723520