Running Away

You are trying to run away from the police after stealing all of the MAPS prize money. The police begin at location 1 on day 0 and MUST move to an adjacent location at the end of each day. On day $d$, how many locations are garunteed to not have police?

Input

The first line contains integers $n,e,d$, the number of locations, edges, and given day. The next $e$ lines contains integers $u,v$, specifying that location $u$ and $v$ are adjacent. It is garunteed that the graph will be connected.

Output

Output the number of locations which are garunteed to not contain police.

Contraints

• $2\le n,e\le {10}^5$
• $1\le u,v\le n$
• $0\le d\le {10}^9$

Example 1

In

10 12 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
7 7
4 6
3 8

Out

7

Example 2

In

20 22 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
17 15
9 1
15 19

Out

10