← 返回题目列表

AtCoder · abc310_d

G. 和平团队

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 体育运动员。

其中,有 M 不兼容的对。的 i- 第不兼容对 (1\leq i\leq M) 是 A_i-th 和 B_i第玩家。

您将把玩家分为 T 团队。 每个球员必须属于一个球队,并且每个球队必须有一名或多名球员。 另外,对于每个 i=1,2,\ldots,M, A_i-th 和 B_i第 名玩家不得属于同一团队。

找出满足这些条件的方法的数量。 在这里,当一个级别中有两名球员属于同一球队而另一个级别属于不同球队时,两个级别被认为是不同的。

约束

  • 1\leq T\leq N\leq10
  • 0\leq M\leq\dfrac{N(N-1)}2
  • 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
  • (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N T M
A _ 1 B _ 1
A _ 2 B _ 2
\vdots
A _ M B _ M

输出

在一行中打印答案。


示例输入 1

5 2 2
1 3
3 4

示例输出 1

4

以下四个分区满足条件。

没有其他除法满足它们,所以打印 4.


示例输入 2

5 1 2
1 3
3 4

示例输出 2

0

可能没有满足条件的划分。


示例输入 3

6 4 0

示例输出 3

65

可能没有不兼容的对。


示例输入 4

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

示例输出 4

8001