Description

DZY热爱化学，他喜欢混合化学物质。

DZY有n种化学物质，其中m对会发生反应。他想把这些化学物质倒入试管中，需要一个接一个地倒入，可以任意顺序。

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

找出在以最佳顺序一个接一个地倒入所有化学物质后的最大可能危险性。

输入

第一行包含两个用空格分隔的整数n和m。

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

考虑所有从1到n编号的化学物质，以某种顺序。

输出

输出一个整数 — 最大可能危险性。

Samples

1 0

1

2 1
1 2

2

3 2
1 2
2 3

4

Note

在第一个示例中，只有一种倒入方式，危险性不会增加。

在第二个示例中，无论我们先倒入第1种化学物质，还是先倒入第2种化学物质，答案始终为2。

在第三个示例中，有四种方式可以达到最大可能危险性：2-1-3、2-3-1、1-2-3和3-2-1（即按倒入顺序排列的化学物质编号）。