Problem1927--最少颜色

1927: 最少颜色

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

给定无向连通图G和m种不同的颜色,用这些颜色为图G的各顶点着色,每个顶点着一种颜色。 
如果有一种着色法使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的。 
求解目标颜色出现最少次数的图的m着色问题。 
输入一张地图(n个顶点),m种颜色(1-m),输入颜色k(1-m),要求使用m种颜色对地图进行着色,并且颜色k出现的次数最少。 

Input

第1行n个顶点(编号1-n),e条边,m种颜色(编号1-m),颜色k 
接下来e行,表示两个顶点之间存在的边 
题目保证:1<=n<=50,n-1<=e<=500 ,1<=k<=m<=10,不存在自环与重边 。

Output

输出k出现的最少次数。 
如果对于给定条件,图的m着色问题无解则输出-1 

Sample Input Copy

4 3 3 1
2 4
1 2
1 3

Sample Output Copy

0