#1298. 图的m着色问题

图的m着色问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定无向连通图G\red{G}m\red{m}种不同的颜色。

用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G\red{G}中每条边的2\red{2}个顶点着不同颜色。

则称这个图是m\red{m}可着色的。

图的m\red{m}着色问题是对于给定图G\red{G}m\red{m}种颜色,找出所有不同的着色法。

对于给定的无向连通图G\red{G}m\red{m}种不同的颜色,编程计算图的所有不同的着色法。

输入格式

第一行3\red{3}个正整数n\red{n},k\red{k}m\red{m},表示给定图G\red{G}n\red{n}个顶点,k\red{k}条边,m\red{m}种颜色。顶点编号为123,n\red{1,2,3,……,n}

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

输出格式

计算出不同的着色方案数

样例

输入样例

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

输出样例

48

数据范围与提示

n<=50\red{n<=50}

k<1000\red{k<1000}

m<10\red{m<10}

中心团队A班 图的存储与遍历

未参加
状态
已结束
规则
IOI
题目
3
开始于
2024-3-9 15:30
结束于
2024-3-13 19:30
持续时间
100 小时
主持人
参赛人数
31