DZY Loves Chemistry

DZY热爱化学.他有n种物质,其中m对会反应.他把它们一种一种倒到烧杯里.有一个危险值,一开始等于1.如果一种物质倒到烧杯里之后至少有一种物质能和它反应,则危险值乘以二;否则危险值不变.求所有物质倒到烧杯里之后最大的危险值. By @Fuko_Ibuki

DZY loves chemistry, and he enjoys mixing chemicals. DZY has $ n $ chemicals, and $ m $ pairs of them will react. He wants to pour these chemicals into a test tube, and he needs to pour them in one by one, in any order. Let's consider the danger of a test tube. Danger of an empty test tube is $ 1 $ . And every time when DZY pours a chemical, if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by $ 2 $ . Otherwise the danger remains as it is. Find the maximum possible danger after pouring all the chemicals one by one in optimal order.

The first line contains two space-separated integers $ n $ and $ m $ . Each of the next $ m $ lines contains two space-separated integers $ x_{i} $ and $ y_{i} $ $ (1<=x_{i}<y_{i}<=n) $ . These integers mean that the chemical $ x_{i} $ will react with the chemical $ y_{i} $ . Each pair of chemicals will appear at most once in the input. Consider all the chemicals numbered from $ 1 $ to $ n $ in some order.

Print a single integer — the maximum possible danger.

1 0

1

2 1
1 2

2

3 2
1 2
2 3

4

In the first sample, there's only one way to pour, and the danger won't increase. In the second sample, no matter we pour the $ 1 $ st chemical first, or pour the $ 2 $ nd chemical first, the answer is always $ 2 $ . In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).