3875: 地图调色板

内存限制:64 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:5 通过:4

题目描述

我买了一个世界地图挂在家里。孩子说:“花花绿绿的挺好看呢!”“你看看颜色有什么不同吗?”“相邻的国家颜色不同!”“是啊,如果把两个相邻的国家涂成相同的颜色,可能会引起严正抗议,甚至战争!”。在地图着色中,为了区分边界,相邻区域是不能有相同颜色的。如果有一张没涂色的地图和m种颜色,怎么涂色才能使相邻区域是不同的颜色呢?

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。
每组测试数据第一行输入结点数n和颜色数m(1<=n,m<=100)。
第2行输入相邻区域数e(边数)(1<=e<=10000)。
接下来有e行,每行输入两个数,代表相邻区域的序号u,v(1<=u,v<=100)。

输出格式

对于每一组输入,输出着色方案数。
每组的输出占一行。

输入样例 复制

2
7 3
12
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5
4 7
5 6
5 7
6 7
5 4
8
1 2
1 3
2 3
2 4
2 5
3 4
3 5
4 5

输出样例 复制

6
48

分类标签