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 guaranteed 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.

Output

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

Constraints

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

Example 1

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

7

Example 2

20 22 6
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

10