寝室管理
时间限制：40s 空间限制：512MB
题目描述
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 1 3 2 4 3 5 4 1 5 2
样例输出
20
提示
N≤100000
K≤N
M=N
题目来源
没有写明来源