Cerința

Într-un oraș sunt n case numerotate de la 1 la n. Între anumite case sunt străzi bidirecționale. În casa cu numărul g locuiește Ghiocel. În celelalte n-1 case locuiesc colegele lui, câte una în fiecare casă. Ghiocel dorește să le ducă ghiocei la începutul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei doar colegelor care stau în case până la care Ghiocel are de parcurs cel mult k străzi. Ajutați-l pe Ghiocel să determine câtor colege ar putea să ducă ghiocei.

Date de intrare

Fișierul de intrare ghiocel2.in conține pe prima linie numerele n m g, reprezentând numărul de case, numărul de străzi și numărul casei în care locuiește Ghiocel. Urmează m linii cu câte două numere i j, cu semnificația: casele i și j sunt legate printr-o stradă bidirecțională. Pe ultima linie se află numărul k.

Date de ieșire

Fișierul de ieșire ghiocel2.out va conține pe prima linie numărul de colege cărora Ghiocel ar putea să le ducă ghiocei.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ n * (n - 1) / 2
• 1 ≤ i, j ≤ n
• 1 ≤ k ≤ n

Exemplu:

ghiocel2.in

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

ghiocel2.out

4

Explicație

Ghiocel locuiește în casa cu numărul 6. Colegele lui stau care stau în casele 1 2 4 și 5 se află la cel mult două de străzi de casa lui Ghiocel. Celelalte colege locuiesc în case mai indepărtate și nu vor primi ghiocei :(