厕所里的OIer

【题目描述】

在n*n(n≤20)个坑的厕所中，某些坑被ZTC等占领，在一行或一列中有两个或以上的OIer，就会发生偷窥事件（ZTC除外,他是个瞎子）。数据一定可以使n个OIer同时上厕所，求n个OIer不发生偷窥事件的位置的方案数。

【输入格式】

第一行n,m 代表n*n的矩阵厕所中有m个坑位被占领。

接下来的m行，每行有两个数代表被占领坑位的坐标。

【输出格式】

一个数，输出n个OIer不发生偷窥事件的位置的方案数

【样例输入】

9 11
7 2
5 8
1 4
3 1
7 6
1 5
3 5
1 8
9 8
5 6
5 8

【样例输出】

100008

【提示】

SCR 状压DP

【来源】

HZOI 2015