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

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

计算出不同的着色方案数

样例

输入样例

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

输出样例

48

数据范围与提示

$\red{n<=50}$

$\red{k<1000}$

$\red{m<10}$