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(即按照倾倒顺序排列的化学品编号)。