99083 - 组合数

从 1 到 N 的整数中挑选一些数,组成集合的方案数是可算的。如果加上 M 个限制:某 2 个数不能 同时选又要怎样计算?

输入

第一行包含 2 个整数 N 和 M,1≤N≤20,1≤M≤400。

下面 M 行,每行 2 个不同的整数 a 和 b 表示这 2 个数不能同时选。1≤a,b≤N,有些限制可能出现多次。

输出

一个整数。

样例

输入

3 2
1 2
2 3

输出

5

输入

3

输出

8

输入

3 3
1 2
1 3
2 3

输出

4
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题