3. 染色问题

【题目描述】

给定一个n个点m条边的联通无向图，给图上每个点染上k种颜色中的一种，且要求每一条边的两个端点不同色（不需要使用全部k种颜色），求方案数 mod1000000007.大样例

【输入格式】

第一行共有三个正整数n、m、k，表示无向图的点数、边数、颜色数。

接下来m行，每行两个整数a与b满足1≤a,b≤n，表示无向图的一条边。

保证无向图联通且无重边、无自环。

【输出格式】

输出一行一个非负整数，表示答案模1000000007 的值。

【样例输入1】

3 3 10
1 2
2 3
3 1

【样例输出1】

720

【样例1说明】

无向图共三个点，两两由一条边相连，即三个点颜色互不相同，答案为10×9×8=720.

【样例输入2】

10 15 20
6 8
5 8
7 8
9 7
2 8
10 9
1 8
3 1
4 9
9 3
7 10
9 8
6 4
2 10
2 9

【样例输出2】

926827429

【数据规模与约定】

20%的数据满足n≤5、m≤10、k≤10.

另外5%的数据满足n≤10、m≤15、k≤1000.

另外10%的数据满足n≤100000、m=n−1、k≤100000，且第 i(1≤i≤n−1) 条边从 i 连向 i+1.

另外15%的数据满足n≤100000、m=n、k ≤100000，且对于 i(1≤i≤n−1) 满足第 i 条边从 i 连向 i+1，且第n条边从n连向1.

另外10%的数据满足n≤1000、m=n+1、k≤100000.

另外30%的数据满足n≤1000、m≤n+5、k≤100000.

对于100%的数据满足n≤100000，m≤n+5，3≤k≤100000.

【来源】

常高4.2