小B旅游
题目描述
aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库小B在一个有N个城市M条道路的国家，每条道路连接的城市可以互相到达且每条道路小B都要花1步去走过它。现在他在1号城市，问他走P步最多能走多少个不同的城市？
输入
aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库输入格式：第1行，三个正整数N、M、P，意义如题：接下来M行，每行两个整数U、V，表示存在一条连接U、V的无向边。
输出
aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库输出格式：1行，一个整数，表示从1号城市出发走P步的所有情况，共能经过多少个不同的城市。
样例输入
4 4 2
1 2
1 3
2 3
3 4
样例输出
4
提示
aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库数据规模：
aYx100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库1<=N<=100000，1<=M<=5000000，1<=P<=10000
