1687 - City

Time Limit : 1 Second

Memory Limit : 512 MB

Submission: 10

Solved: 5

Description

In the old days, there are N cities connected by M one-way roads. You can go from any city to any other city . 


Unfortunately, the war began and one of the cities was attacked. If one city is under attack, people won't go to that city for their safety. Now pyy wanted to know after a particular city was attacked, how many pairs of city(beside the city which was attacked) would become separated. We consider city x and city y is separated if we can't go to y from x or go to x from y.


 

Input

We have multiply cases. For each case:


The first line contains three numbers:


  N -- the number of cities (0 < N <= 1000)


  M -- the number of roads (0 < M <= 2000)


  P -- the label of city which was under attack.(1 <= P <= N)


From second to M+1 lines, each line contains 2 numbers, xi, yi, representing a road from x to y. (1 <= xi, yi <= N)

Output

For each case, output one integer, the number of pairs.

sample input
4 4 2
1 2
2 3
3 4
4 1
sample output
3
hint

Each pair of cities is separated.

source
© 2015 HUST ACMICPC TEAM. All Right Reserved.