地图填色(Map Coloring)

题目描述

地图中有 m 个省份（编号 1~m），现请你用 n 种颜色给这 m 个省份填上颜色。要求：每个省份用一种颜色，且任意两个相邻省份的颜色不能相同。问一共有多少种不同的填色方案？

输入数据将给出颜色的数量 n、省份的数量 m，以及 k 个相邻关系 x-y（表示 x 省和 y 省相邻）。

输入格式

第一行三个整数 n、m、k，分别表示颜色数量、省份数量和相邻关系数量。

接下来 k 行，每行两个整数 x 和 y，表示省份 x 与省份 y 相邻。

输出格式

一个整数，表示不同的填色方案总数。

样例输入

4 4 4
1 2
1 4
2 3
3 4

样例输出

84

数据范围

1 ≤ n, m ≤ 20，0 ≤ k ≤ m×(m-1)/2。