题目描述

给定无向连通图 G 和 $m$ 种不同的颜色，用这些颜色给图的各个顶点着一种颜色，若某种方案使得图中每条边的 $2$ 个顶点的颜色都不相同，则是一个满足的方案，找出所有的方案。

输入输出格式

输入

第一行有 3 个正整数 $n(n<=100),k$ 和 $m(m<=5)$，分别表示 $n$ 个顶点，$k$ 条边，$m$ 种颜色。

接下来 $k$ 行，每行 2 个正整数，表示一条边的两个顶点。

输出

输出所有不同的着色方案数。

样例

输入1

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

输出1

48