题目描述

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

输入格式

第1行有3个整数n、k和m，表示给定的图G有n个顶点、K条边、m种颜色，顶点的编号为1、2、3、4.....n。在接下来的k行种每行有两个整数u、v，表示图G的一条边(u,v)。

输出格式

程序运行结束时将计算出的不同着色方案数输出。如果不能着色，则程序输出-1。

样例

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

48