CF445B DZY Loves Chemistry

DZY 喜欢化学，他喜欢混合化学药品。 DZY 有 $n$ 种化学药品，其中有 $m$ 对药品会发生反应。他想把这些化学药品依次倒入试管中，每次可以选择任意顺序倒入。 我们来定义一个试管的危险值。空试管的危险值为 $1$。每当 DZY 倒入一种化学药品时，如果试管中已经存在一种或多种可以与它反应的药品，试管的危险值就会乘以 $2$，否则危险值保持不变。 请你求出，依照最优顺序倒入所有药品后，试管最终可能达到的最大危险值。

第一行包含两个用空格分隔的整数 $n$ 和 $m$。 接下来的 $m$ 行，每行包含两个用空格分隔的整数 $x_{i}$ 和 $y_{i}$，表示化学药品 $x_{i}$ 会与化学药品 $y_{i}$ 反应。每对药品在输入中最多只出现一次。 所有药品编号从 $1$ 到 $n$。 $1 \leq n \leq 50;\ 0 \leq m \leq \frac{n(n - 1)}{2}$

输出一个整数，表示最大可能的危险值。

在第一个样例中，只有一种倒入方式，危险值不会提高。 在第二个样例中，无论是先倒第 $1$ 种化学药品还是先倒第 $2$ 种化学药品，答案始终是 $2$。 在第三个样例中，有 4 种方式可以达到最大危险值：2-1-3、2-3-1、1-2-3 和 3-2-1（即倒入药品的顺序）。 由 ChatGPT 5 翻译