问题描述
给定无向连通图 $G$ 和 $m$ 种不同的颜色。用这些颜色为图 $G$ 的各顶点着色,每个顶点着一种颜色。如果有一种着色法使 $G$ 中每条边的 2 个顶点着不同颜色,则称这个图是“m可着色”的。图的 m 着色问题是对于给定图 $G$ 和 $m$ 种颜色,找出所有不同的着色法。
对于给定的无向连通图 $G$ 和 $m$ 种不同的颜色,编程计算图的所有不同的着色法。
输入格式
第 1 行有 3 个正整数 $n$,$k$ 和$m$,表示给定的图 $G$ 有 $n$ 个顶点和 $k$ 条边,$m$种颜色。顶点编号为 $1,2,…,n$。接下来的 $k$ 行中,每行有 2 个正整数 $u$,$v$,表示图 $G$ 的一条边 $(u,v)$。
输出格式
一行,一个整数,即不同的方案数。
样例一
input
5 8 4 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5
output
48
数据范围与约定
时间限制: $1\mathrm{s}$
内存限制: $256\mathrm{MB}$