AT_abc310_d [ABC310D] Peaceful Teams

题目描述

有 $N$ 名运动员。

在这 $N$ 名运动员中，有 $M$ 对互相不合的运动员，第 $i\ (1\leq i\leq M)$ 对为第 $A_i$ 名运动员和第 $B_i$ 名运动员。

你需要将这些运动员分成 $T$ 个队伍。每名运动员必须恰好属于一个队伍，并且每个队伍中至少要有一名运动员。此外，对于每个 $i=1,2,\ldots,M$，第 $A_i$ 名运动员和第 $B_i$ 名运动员不能被分在同一个队伍中。

请计算满足上述条件的分队方案有多少种。注意，如果存在一对运动员，在一种分队方案中他们属于同一个队伍，而在另一种分队方案中他们属于不同队伍，则这两种分队方案被认为是不同的。

输入格式

输入通过标准输入按以下格式给出。

$N$ $T$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

5 2 2
1 3
3 4

输出 #1

4

输入输出样例 #2

输入 #2

5 1 2
1 3
3 4

输出 #2

0

输入输出样例 #3

输入 #3

6 4 0

输出 #3

65

输入输出样例 #4

输入 #4

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

输出 #4

8001

说明/提示

限制条件

• $1\leq T\leq N\leq 10$
• $0\leq M\leq\dfrac{N(N-1)}{2}$
• $1\leq A_i < B_i \leq N\ (1\leq i\leq M)$
• $(A_i,B_i)\neq (A_j,B_j)\ (1\leq i<j\leq M)$
• 所有输入均为整数

样例解释 1

满足条件的分队方案共有 $4$ 种。

不存在其他满足条件的分队方案，因此请输出 $4$。

样例解释 2

也有可能不存在任何满足条件的分队方案。

样例解释 3

也有可能不存在任何互相不合的运动员对。

由 ChatGPT 4.1 翻译