#3648. 寝室管理

内存限制:512 MiB 时间限制:40 Sec

题目描述

T64有一个好朋友,叫T128。T128是寄宿生,并且最近被老师叫过去当宿管了。宿管可不是一件很好做的工作,碰
巧T128有一个工作上的问题想请T64帮忙解决。T128的寝室条件不是很好,所以没有很多钱来装修。礼间寝室仅由n
-1条双向道路连接,而且任意两间寝室之间都可以互达。最近,T128被要求对一条路径上的所有寝室进行管理,这
条路径不会重复经过某个点或某条边。但他不记得是哪条路径了。他只记得这条路径上有不少于k个寝室。于是,
他想请T64帮忙数一下,有多少条这样的路径满足条件。嗯…还有一个问题。由于最近有一些熊孩子不准晚上讲话
很不爽,他们决定修筑一条“情报通道”,如果通道建成,寝室就变成了一个N个点N条边的无向图。并且,经过“
情报通道”的路径也是合法的。T128心想:通道建成之前,T64还有一个高效的算法帮我数路径条数,但是通道建
成之后,他还有办法吗?对,T64手忙脚乱,根本数不清有多少条路径。于是他找到了你。

输入格式

第一行为三个正整数N,M,K(2 ≤ K ≤ N),代表有n间寝室,m条边连接它们n-1 ≤ m ≤ N;
m= n-1意味着“情报遁道”未被修好;m=n意味着“情报通道”已被修好),以及题目描述中的K。
接下来m行,每行两个正整数z,y,代表第x间寝室与第y间寝室之间有一条双向边。

输出格式

仅包含一个整数,代表经过至少K间寝室的路径条数。

样例

样例输入


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

样例输出


			
20

数据范围与提示



N≤100000     

K≤N

M=N