Problem C: 2016NHOI初中 第三题 组合数（3.3）

Problem C: 2016NHOI初中 第三题 组合数（3.3）

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 1Submit: 7Statistics

Description

从 1 到 N 的整数中挑选一些数，组成集合的方案数是可算的。如果加上 M 个限制：某 2 个数不能同时选又要怎样计算？ （1个都不选的也算一种方案）

Input

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

Output

一个整数。

Sample Input Copy 

3 2
1 2
2 3

Sample Output Copy 

5

HINT

样例输入2
3 3
1 2
1 3
2 3
样例输出2
4
Submit