Magic Bracelet
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一个长度为n的环形珍珠项链，有m种颜色，每个珍珠可以任选一种颜色染色，但是规定了k对禁止关系(a,b)，即不能存在颜色分别为 a,b 的珍珠相邻。
问可以有多少种染色方法可以得到本质不同的珍珠项链(通过旋转得到的项链为本质相同)，输出后的结果。

输入描述:

第一行一个正整数，表示T组数据。
对于每组数据：
第一行三个整数，。
接下来k行，每行两个整数。
保证

输出描述:

输出T行，每一行输出一个整数表示答案。
示例1

输入

复制 
4
3 2 0
3 2 1
1 2
3 2 2
1 1
1 2
3 2 3
1 1
1 2
2 2

输出

复制 
4
2
1
0

备注:

原题链接：http://poj.org/problem?id=2888