Peaceful Teams

题目描述

有 $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$

输出格式

在一行中打印答案。

5 2 2
1 3
3 4

4

5 1 2
1 3
3 4

0

6 4 0

65

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

8001

提示

$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)$ 所有输入值均为整数。下述四种划分满足条件。 没有其他划分满足条件，所以输出 $4$.
可能没有满足条件的划分。
可能没有不相容的选手对。

标签: AtCoder|abc310D

来源

AtCoder|abc310D