Un teren de paintball este reprezentat prin n zone de luptă, numerotate de la 1 la n, interconectate prin tuneluri bidirecționale. Luptele pot avea loc doar în cele n zone; traversarea unui tunel, între două zone învecinate, durează un minut, iar traversarea unei zone se face instantaneu.

La joc participă trei jucători: doi jucători roșii, care se pot deplasa prin terenul de joc, folosind rețeaua de tuneluri, și un jucător albastru, Blue, care se află în zona de luptă b și nu o poate părăsi. Blue este mai puternic decât oricare dintre cei doi jucători roșii și orice luptă dintre Blue și un jucător roșu va fi câștigată de Blue. Jucătorii roșii pot câștiga numai dacă îl atacă pe Blue în același timp.

Jocul se desfășoară în felul următor:

• jucătorii roșii intră pe teren în două zone diferite ale acestuia;
• fiecare se deplasează spre zona de luptă a lui Blue, pe cel mai rapid drum, parcurgând un tunel într-un minut;
• când un jucător roșu ajunge în zona lui Blue, are loc lupta.

Cerinţa

Determinați în câte moduri pot fi alese zonele inițiale pentru jucătorii roșii, astfel încât să, mergând pe drumul cel mai scurt spre zona b a lui Blue, să ajungă în același timp și să îl învingă.

Date de intrare

Fișierul de intrare paintball.in conține pe prima linie numerele n m b, reprezentând numărul de vârfuri ale zone de luptă, numărul de tuneluri și numărul zonei unde se află Blue. Următoarele m linii conțin câte o pereche de numere i j, cu semnificația că există tunel bidirecțional de la zona de luptă i la zona de luptă j.

Date de ieșire

Fişierul de ieșire paintball.out va conține pe prima linie numărul NRP de modalități în care pot fi alese zonele inițiale pentru jucătorii roșii.

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• 1 ≤ k ≤ n
• 1 ≤ i , j ≤ n

Exemplu:

paintball.in

7 8 3
1 4
2 3
2 4
3 6 
3 7
4 5
4 6 
4 7

paintball.out

4

Perechile de zone de unde pot începe jucătorii roșii sunt: 1 5, 2 6, 2 7 și 6 7.