A9501 | DZY Loves Chemistry

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.