题目描述

小B在一个有n个城市m条道路的国家，每条道路连接的城市可以互相到达且每条道路小B都要花1步去走过它。现在他在1号城市，问他走p步最多能走到多少个不同的城市?

输入格式:

第1行，三个正整数n,m,p，意义如题;接下来m行，每行两个整数u,v，表示存在一条连接u,v的无向边。

输出格式:

1行，一个整数ans,表示走p步最多能走多少个不同的城市。

样例:

4 4 2
1 2
1 3
2 3
3 4

4

数据规模:

$n<= 100000, m<=1000000,p<=10000$

Limitation

1s, 1024KiB for each test case.