3. 染色问题

【题目描述】

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

【输入格式】

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

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

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

【输出格式】

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

【样例输入1】

3 3 10
1 2
2 3
3 1

【样例输出1】

720

【样例1说明】

无向图共三个点，两两由一条边相连，即三个点颜色互不相同，答案为 $10\times 9\times 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\le 5,m≤10,k≤10$。

另外 $5\%$ 的数据满足 $n\le 10,m\le 15,k\le 1000$。

另外 $10\%$ 的数据满足 $n\le 100000,m=n−1,k\le 100000$，且第 $i(1\le i\le n−1)$ 条边从 $i$ 连向 $i+1$。

另外 $15\%$ 的数据满足 $n\le 100000,m=n,k \le 100000$，且对于 $i(1\le i\le n−1)$ 满足第 $i$ 条边从 $i$ 连向 $i+1$，且第 $n$ 条边从 $n$ 连向 $1$。

另外 $10\%$ 的数据满足 $n\le 1000,m=n+1,k\le 100000$。

另外 $30\%$ 的数据满足 $n\le 1000,m\le n+5,k\le 100000$。

对于 $100\%$ 的数据满足 $n\le 100000,m\le n+5,3\le k\le 100000$。

【来源】

常高 4.2。