3. 棋盘放車

【题目描述】

在$n*n(n≤20)$的方格棋盘上放置$n$个象棋的車，某些格子不能放，求使它们不能互相攻击的方案总数。

【输入格式】

输入文件第一行，有两个数 $n$ 、 $m$ ，$n$表示方格棋盘大小,$m$表示不能放的格子数量

下面有$m$行,每行两个整数,为不能放的格子的位置的行列号。

【输出格式】

输出文件也只有一行，即得出的方案总数。

【输入样例】

2 1
1 1

【输出样例】

1