题目描述

独立集是一个图论中的概念，是指图 $G$ 中两两互不相连的顶点构成的集合。 最大独立集就是图 $G$ 的所有独立集中，点数最多的那个独立集

现在徐老师想知道，对于一个给定的图 $G$

所有 $G$ 的子图 $G'$ 的最大独立集大小之和是多少

例如 $G$ 有三个子图 $G1,G2,G3$，最大独立集大小分别为 $cnt1,cnt2,cnt3$

徐老师想问的答案就是 $ans=cnt1+cnt2+cnt3$

输入格式

输入第一行包含两个整数 $n,m$ 表示图 $G$ 有 $n$ 个顶点和 $m$ 条无向边

接下来 $m$ 行，每行包含两个整数 $u,v$ 表示这条边连接的两个顶点编号

输出格式

输出一个整数表示答案

数据范围

对于 $20\%$ 的数据满足 $1 \leq n \leq 5$

对于 $50\%$ 的数据满足 $1 \leq n \leq 18$

对于 $100\%$ 的数据满足 $1 \leq n \leq 26, 0 \leq u,v < n$

题目保证输入的图中不存在重边和自环

样例输入1

3 2
0 1
0 2

样例输出1

9

样例解释1

这个图一共有 $8$ 个子图 对于 $G1={}$ 来说，最大独立集的大小为 $0$ 对于 $G2={0}$ 来说，最大独立集的大小为 $1$ 对于 $G3={1}$ 来说，最大独立集的大小为 $1$ 对于 $G4={2}$ 来说，最大独立集的大小为 $1$ 对于 $G5={0,1}$ 来说，最大独立集的大小为 $1$ 对于 $G6={0,2}$ 来说，最大独立集的大小为 $1$ 对于 $G7={1,2}$ 来说，最大独立集的大小为 $2$ 对于 $G8={0,1,2}$ 来说，最大独立集的大小为 $2$ 最后答案为 $0+1+1+1+1+1+2+2=9$

样例输入2

7 5
0 5
3 4
1 2
2 5
0 2

样例输出2

328