Description

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

Input Format

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

Output Format

程序运行结束时，将计算出的不同的着色方案数输出。

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

48

Hint

数据保证，$1\leq n\leq 100$，$1 \leq k\leq 2500$。

在 $n$ 很大时保证 $k$ 足够大。

保证答案不超过 $20000$。

数据为在满足上述条件的合法数据中随机采样得到。