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

Input

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

Output

7

Example 2

Input

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

Output

10