2846. 图的m着色问题

【题目描述】

给定无向连通图G和$m$种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是$m$可着色的。

图的$m$着色问题是对于给定图G和$m$种颜色，找出所有不同的着色法。

【输入格式】

第1行有$3$个正整数$n,k,m(n\leq 100,k\leq 3000,m\leq 6)$，表示给定的图G有$n$个顶点和$k$条边，$m$种颜色，顶点编号为$1,2,\cdots,n$。

接下来$k$行中，每行有$2$个正整数$u,v$，表示图G的一条边$(u,v)$。

【输出格式】

输出计算出的不同的着色方案数。

【样例输入】

5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

【样例输出】

48