1273: [蓝桥杯2015决赛]模型染色
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：26
通过：10
题目描述
在电影《超能陆战队》中，小宏可以使用他的微型机器人组合成各种各样的形状。
现在他用他的微型机器人拼成了一个大玩具给小朋友们玩。为了更加美观，他决定给玩具染色。
小宏的玩具由n个球型的端点和m段连接这些端点之间的边组成。
下图给出了一个由5个球型端点和4条边组成的玩具，看上去很像一个分子的球棍模型。
由于小宏的微型机器人很灵活，这些球型端点可以在空间中任意移动
同时连接相邻两个球型端点的边可以任意的伸缩，这样一个玩具可以变换出不同的形状。
在变换的过程中，边不会增加，也不会减少。
小宏想给他的玩具染上不超过k种颜色，这样玩具看上去会不一样。
如果通过变换可以使得玩具变成完全相同的颜色模式，则认为是本质相同的染色。
现在小宏想知道，可能有多少种本质不同的染色。
现在他用他的微型机器人拼成了一个大玩具给小朋友们玩。为了更加美观，他决定给玩具染色。
小宏的玩具由n个球型的端点和m段连接这些端点之间的边组成。
下图给出了一个由5个球型端点和4条边组成的玩具，看上去很像一个分子的球棍模型。
由于小宏的微型机器人很灵活，这些球型端点可以在空间中任意移动
同时连接相邻两个球型端点的边可以任意的伸缩，这样一个玩具可以变换出不同的形状。
在变换的过程中，边不会增加，也不会减少。
小宏想给他的玩具染上不超过k种颜色，这样玩具看上去会不一样。
如果通过变换可以使得玩具变成完全相同的颜色模式，则认为是本质相同的染色。
现在小宏想知道，可能有多少种本质不同的染色。
输入格式
输入的第一行包含三个整数n, m, k(1<=n<=10,1<=m<=45,1<=k<=30)
分别表示小宏的玩具上的端点数、边数和小宏可能使用的颜色数。端点从1到n编号。
接下来m行每行两个整数a, b，表示第a个端点和第b个端点之间有一条边。输入保证不会出现两条相同的边。
分别表示小宏的玩具上的端点数、边数和小宏可能使用的颜色数。端点从1到n编号。
接下来m行每行两个整数a, b，表示第a个端点和第b个端点之间有一条边。输入保证不会出现两条相同的边。
输出格式
输出一行，表示本质不同的染色的方案数。由于方案数可能很多，请输入方案数除10007的余数。
输入样例 复制
3 2 2
1 2
3 2输出样例 复制
6数据范围与提示
令(a, b, c)表示第一个端点染成a，第二个端点染成b，第三个端点染成c
则下面6种本质不同的染色：(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 2), (2, 2, 2)。
而(2, 1, 1)与(1, 1, 2)是本质相同的，(2, 2, 1)与(1, 2, 2)是本质相同的。
则下面6种本质不同的染色：(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 2), (2, 2, 2)。
而(2, 1, 1)与(1, 1, 2)是本质相同的，(2, 2, 1)与(1, 2, 2)是本质相同的。