← 返回题目列表

Codeforces · 445/B

B. DZY 热爱化学

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

DZY 热爱化学,他喜欢混合化学品。

DZY 有 n 种化学物质,其中 m 对会发生反应。他要把这些化学物质倒入试管中,而且需要一一倒入,顺序不限。

让我们考虑一下试管的危险。空试管的危险性为1。而DZY每次倒入化学品时,如果试管内已经有一种或多种化学品可以与其发生反应,则试管的危险性将乘以2。否则危险性保持不变。

将所有化学品按照最佳顺序一一倒入后,找出最大可能的危险。

输入

第一行包含两个空格分隔的整数 n 和 m $$( 1 \leq n \leq 50 ; \; 0 \leq m \leq \frac { n ( n - 1 ) } { 2 } )$$。

接下来的 m 行中的每一行都包含两个空格分隔的整数 xi 和 yi (1 ≤ xi < yi ≤ n)。这些整数意味着化学物质 xi 将与化学物质 yi 发生反应。每对化学物质在输入中最多出现一次。

按某种顺序考虑从 1 到 n 编号的所有化学品。

输出

打印一个整数——最大可能的危险。

示例

输入 #1

1 0

输出 #1

1

输入 #2

2 1
1 2

输出 #2

2

输入 #3

3 2
1 2
2 3

输出 #3

4

注意

在第一个样本中,只有一种倾倒方式,并且危险不会增加。

在第二个样品中,无论我们先倒入第一种化学品,还是先倒入第二种化学品,答案始终是 2。

在第三个样本中,有四种方法可以达到最大可能的危险:2-1-3、2-3-1、1-2-3和3-2-1(即按照倾倒顺序排列的化学品编号)。