说明

我买了一个世界地图挂在家里。孩子说：“花花绿绿的挺好看呢！”“你看看颜色有什么不同吗？”“相邻的国家颜色不同！”“是啊，如果把两个相邻的国家涂成相同的颜色，可能会引起严正抗议，甚至战争！”。在地图着色中，为了区分边界，相邻区域是不能有相同颜色的。如果有一张没涂色的地图和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

来源

《趣学算法》5.4节