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
input=lambda:sys.stdin.readline().rstrip()
sys.setrecursionlimit(50000)

# 強連結成分分解(SCC): グラフGに対するSCCを行う
# 入力: <N>: 頂点サイズ, <G>: 順方向の有向グラフ, <RG>: 逆方向の有向グラフ
# 出力: (<ラベル数>, <各頂点のラベル番号>)
def scc(N, G, RG):
  order = []
  used = [0]*N
  group = [None]*N
  def dfs(s):
    used[s] = 1
    for t in G[s]:
      if not used[t]:
        dfs(t)
    order.append(s)
  def rdfs(s, col):
    group[s] = col
    used[s] = 1
    for t in RG[s]:
      if not used[t]:
        rdfs(t, col)
  for i in range(N):
    if not used[i]:
      dfs(i)
  used = [0]*N
  label = 0
  for s in reversed(order):
    if not used[s]:
      rdfs(s, label)
      label += 1
  return label, group

# 縮約後のグラフを構築
def construct(N, G, label, group):
  G0 = [[] for i in range(label)]
  GP = [[] for i in range(label)]
  for v in range(N):
    lbs = group[v]
    for w in G[v]:
      lbt = group[w]
      if lbs == lbt:
        continue
      G0[lbs].append(lbt)
    GP[lbs].append(v)
  return G0, GP

n,m,s=map(int,input().split())
s-=1
edge=[[]for _ in range(n)]
redge=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  redge[b].append(a)
label,group=scc(n,edge,redge)
a,b=construct(n,redge,label,group)
ans=0
for i in range(label):
  if len(a[i])==0:
    ans+=(i!=group[s])
print(ans)