暂无测试数据。

题目描述

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

输入

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

输出

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

样例输入

4 4 2
1 2
1 3
2 3
3 4

样例输出

4

数据范围限制

\(n \leq 10^5\),\(m \leq 5 \times 10^5\),\(p \leq 10^4\)

来源

基础篇练习6.1