问题描述

给定无向连通图 $G$ 和 $m$ 种不同的颜色。用这些颜色为图 $G$ 的各顶点着色，每个顶点着一种颜色。如果有一种着色法使 $G$ 中每条边的 2 个顶点着不同颜色，则称这个图是“m可着色”的。图的 m 着色问题是对于给定图 $G$ 和 $m$ 种颜色，找出所有不同的着色法。

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

输入格式

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

输出格式

一行，一个整数，即不同的方案数。

样例一

input

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

output

48

数据范围与约定

时间限制： $1\mathrm{s}$

内存限制： $256\mathrm{MB}$