Description

Rin 有一个 $n$ 个点 $m$ 条边的无向图，点的编号为 $1\sim n$。

给定正整数 $k$，Rin 想知道所有包含 $1$ 的 $k$ 元环的个数。请你帮帮她。

Format

Input

第一行三个正整数 $n,m,k$。

下面 $m$ 行，每行两个正整数 $u,v$，表示一条无向边 $(u,v)$。

Output

一行一个正整数，即答案。

Samples

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

1

Limitation

对于所有数据，$1\le n,m\le 10^5$，$1\le k\le 30$，$1\le u,v\le n$。

本题开启捆绑测试。

• Subtask 1（30 pts）：满足 $1\le n,m,k\le 5$。
• Subtask 2（70 pts）：无特殊限制。