8949: Subdivision

You are given a graph with n vertices and $m$ undirected edges of length $1$. You can do the following operation on the graph for arbitrary times:

Choose an edge (u,v) and replace it by two edges, (u,w) and (w,v), where w is a newly inserted vertex. Both of the two edges are of length $1$.

You need to find out the maximum number of vertices whose minimum distance to vertex $1$ is no more than $k$.

The first line contains three integers n (1≤n≤10^5), m (0≤m≤2⋅10^5) and k (0≤k≤10^9).
Each of the next $m$ lines contains two integers $u$ and v (1≤u,v≤n), indicating an edge between $u$ and $v$. It is guaranteed that there are no self-loops or multiple edges.

Output an integer indicating the maximum number of vertices whose minimum distance to vertex $1$ is no more than $k$.

Here is the illustration for the second example.