NN 个人围坐一圈，有 MM 对朋友关系。
第 ii 对朋友关系是指，编号是 aiai 的人和编号是 bibi 的人是朋友。
现在要给他们安排座位，要求所有相邻的人不能是朋友。
问共有多少种方案？
如果两个方案只有旋转角度不同，则我们将其视为一种方案。

输入格式

第一行包含两个整数 N,MN,M。
接下来 MM 行，每行包含一对 ai,biai,bi。

输出格式

输出一个数，表示总方案数。

数据范围

3≤N≤103≤N≤10,
0≤M≤N(N−1)20≤M≤N(N−1)2,
1≤ai(ai,bi)≠(aj,bj)(ai,bi)≠(aj,bj),
所有输入均为整数。

输入样例1：

4 1 1 2

输出样例1：

2

输入样例2：

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

输出样例2：

112512

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 11;
  9. bool g[N][N], st[N]; // g[i][j]表示i 与 j的关系
  10. int n, m;
  11. int pos[N]; // 下标上是谁
  12. int res = 0;
  14. void dfs(int u) {
  15.     if (u == n) {
  16.         if (g[pos[n - 1]][pos[0]]) return;
  17.         res ++;
  18.         return;
  19.     }
  20.     for (int i = 1; i <= n; ++i) {
  21.         if (!st[i] && !g[i][pos[u - 1]]) {
  22.             st[i] = true;
  23.             pos[u] = i;
  24.             dfs(u + 1);
  25.             st[i] = false;
  26.         }
  27.     }
  28. }
  30. int main() {
  31.     cin >> n >> m;
  32.     while (m --) {
  33.         int a, b;
  34.         cin >> a >> b;
  35.         g[a][b] = true; g[b][a] = true;
  36.     }
  37.     pos[0] = 1;
  38.     st[1] = true;
  39.     dfs(1);
  40.     cout << res << endl;
  41.     return 0;
  42. }