和平分组

题目描述

有 $N$ 名运动员。

其中有 $M$ 对互不相容的组合。第 $i$ 对互不相容的组合 $(1 \le i \le 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

满足条件的分组方式有以下 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 \le T \le N \le 10$
• $0 \le M \le \dfrac{N(N-1)}{2}$
• $1 \le A_i \lt B_i \le N\ (1 \le i \le M)$
• $(A_i,B_i) \ne (A_j,B_j)\ (1 \le i \lt j \le M)$
• 输入中的所有值均为整数。