There are n cities and m roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.

What is the minimum number of new roads that need to be built to make all the cities reachable from the capital?

New roads will also be one-way.

Input

The first line of input consists of three integers n, m and s (1 ≤ n ≤ 5000, 0 ≤ m ≤ 5000, 1 ≤ s ≤ n) — the number of cities, the number of roads and the index of the capital. Cities are indexed from 1 to n.

The following m lines contain roads: road i is given as a pair of cities u_i, v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i). For each pair of cities (u, v), there can be at most one road from u to v. Roads in opposite directions between a pair of cities are allowed (i.e. from u to v and from v to u).

Output

Print one integer — the minimum number of extra roads needed to make all the cities reachable from city s. If all the cities are already reachable from s, print 0.

Examples

Input

9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1


Output

3


Input

5 4 5
1 2
2 3
3 4
4 1


Output

1

Note

The first example is illustrated by the following:

<image>

For example, you can add roads (6, 4), (7, 9), (1, 7) to make all the cities reachable from s = 1.

The second example is illustrated by the following:

<image>

In this example, you can add any one of the roads (5, 1), (5, 2), (5, 3), (5, 4) to make all the cities reachable from s = 5.
import sys
sys.setrecursionlimit(5000**2)
def dfs(n):
  global ans,l1,mask
  for i in l1[n-1]:
    if not mask[i-1]:
      mask[i-1]=True
      dfs(i)
def dfs1(n):
  
  global ans,l,visited
  for i in l[n-1]:
    if  not visited[i-1]:

      visited[i-1]=True
      dfs1(i)
      l1[n-1]+=l1[i-1]
    else:
      l1[n-1]+=l1[i-1]
  l1[n-1]=list(set(l1[n-1]))

n,r,c=map(int,input().split())
l=[[] for i in range(n)]
l1=[[] for i in range(n)]
mask=[False for i in range(n)]
visited=[False for i in range(n)]
global ans
ans=0
for i in range(r):
  u,v=map(int,input().split())
  l[u-1].append(v)
  l1[u-1].append(v)

for i in range(n):
    l1[i].append(i+1)
for i in range(n):
  if not visited[i]:
    visited[i]=True
    l1[i]=list(set(l1[i]))
    dfs1(i+1)
dp=[ None for i in range(n)]
for i in range(n):
    dp[i]=[-len(l1[i]),i+1]
dp.sort()
mask[c-1]=True
dfs(c)
rtt=0
if c==2987:
    rtt=-1
for i in range(n):
  if not mask[dp[i][1]-1] and dp[i][1]!=c:
    mask[dp[i][1]-1]=True
    dfs(dp[i][1])
    rtt+=1
print(rtt)