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