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 \le n \le 5000, 0 \le m \le 5000, 1 \le s \le 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 \le u_i, v_i \le n$, $u_i \ne 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$.

Difficulty: introductory

Starter code:

Solutions:

from queue import Queue
from random import shuffle
import sys
import math
import os.path


sys.setrecursionlimit(100000)

# LOG

def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT

def ni():
    return map(int, input().split())


def nio(offset):
    return map(lambda x: int(x) + offset, input().split())


def nia():
    return list(map(int, input().split()))


# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def toMapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}


# SORT
def sortId(arr):
    return sorted(range(len(arr)), key=lambda k: arr[k])


# MAIN

n,m,s = ni()

s -= 1

adj = [[] for _ in range(n)]

for i in range(m):
    u,v = nio(-1)
    if (v != s):
        adj[u].append(v)

stack = []

visited= [False]*n

def dfs(x):
    nonlocal visited
    nonlocal stack
    visited[x] = True
    for y in adj[x]:
        if not visited[y]:
            dfs(y)

    stack.append(x)


for i in range(n):
    if not visited[i]:
        dfs(i)

# log(adj)
# log(visited)
# log(stack)

count = -1

def loang(x):
    nonlocal visited
    visited[x] = False
    for y in adj[x]:
        if visited[y]:
            loang(y)


for x in stack[::-1]:
    if visited[x]:
        count += 1
        loang(x)

print(count)


from queue import Queue
from random import shuffle
import sys
import math
import os.path


sys.setrecursionlimit(10**9)

# LOG

def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT

def ni():
    return map(int, input().split())


def nio(offset):
    return map(lambda x: int(x) + offset, input().split())


def nia():
    return list(map(int, input().split()))


# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def toMapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}


# SORT
def sortId(arr):
    return sorted(range(len(arr)), key=lambda k: arr[k])


# MAIN

n,m,s = ni()

s -= 1

adj = [[] for _ in range(n)]

for i in range(m):
    u,v = nio(-1)
    if (v != s):
        adj[u].append(v)

stack = []

visited= [False]*n

def dfs(x):
    nonlocal visited
    nonlocal stack
    visited[x] = True
    for y in adj[x]:
        if not visited[y]:
            dfs(y)

    stack.append(x)


for i in range(n):
    if not visited[i]:
        dfs(i)

# log(adj)
# log(visited)
# log(stack)

count = -1

def loang(x):
    nonlocal visited
    visited[x] = False
    for y in adj[x]:
        if visited[y]:
            loang(y)


for x in stack[::-1]:
    if visited[x]:
        count += 1
        loang(x)

print(count)

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m, s = list(map(int, input().split()))
s = s - 1


def read_graph():
    g = defaultdict(list)
    for _ in range(m):
        (u, v) = [int(x) - 1 for x in input().split()]
        if v != s:
            g[u].append(v)
    return g


G = read_graph()
vis = defaultdict(lambda: False)
topo = []


def dfs(u):
    # print(u)
    for v in G[u]:
        if not vis[v]:
            vis[v] = True
            dfs(v)
    topo.append(u)


for i in range(n):
    if not vis[i]:
        vis[i] = True
        dfs(i)

vis.clear()
vis[s] = True
dfs(s)
ans = 0
for i in topo[::-1]:
    if not vis[i]:
        vis[i] = True
        ans += 1
        dfs(i)

print(ans)


from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m, s = list(map(int, input().split()))
s = s - 1


def read_graph():
    g = defaultdict(list)
    for _ in range(m):
        (u, v) = [int(x) - 1 for x in input().split()]
        # if v != s:
        g[u].append(v)
    return g


G = read_graph()
vis = defaultdict(lambda: False)
topo = []


def dfs(u):
    # print(u)
    for v in G[u]:
        if not vis[v]:
            vis[v] = True
            dfs(v)
    topo.append(u)


for i in range(n):
    if not vis[i]:
        vis[i] = True
        dfs(i)

vis.clear()
vis[s] = True
dfs(s)
ans = 0
for i in topo[::-1]:
    if not vis[i]:
        vis[i] = True
        ans += 1
        dfs(i)

print(ans)


import sys


def dfs(u):
    avail[u] = False
    for v in g[u]:
        if avail[v]:
            dfs(v)
    topo.append(u)


sys.setrecursionlimit(6000)
n, m, s = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
avail, topo = [True] * n, []
for i,a in enumerate(avail):
    if a:
        dfs(i)
avail, res = [True] * n, 0
dfs(s - 1)
for i in reversed(topo):
    if avail[i]:
        res += 1
        dfs(i)
print(res)

import sys

N = 5000 + 5
adj = [[] for i in range(N)]
mark = [0 for i in range(N)]
topo = []
sys.setrecursionlimit(6000)
#fin = open("999E.inp", "r")
#fou = open("999E.out", "w")
#n, m, s = map(int, fin.readline().split())
n, m, s = list(map(int, input().split()))
for i in range(m):
	#u, v = map(int, fin.readline().split())
	u, v = list(map(int, input().split()))
	adj[u].append(v)

def topoSort(u):
	mark[u] = 1
	for j in range(len(adj[u])):
		v = adj[u][j]
		if (mark[v] == 0): topoSort(v)
	topo.append(u)

def dfs(u):
	mark[u] = 1
	for j in range(len(adj[u])):
		v = adj[u][j]
		if (mark[v] == 0): dfs(v)

for i in range(1, n+1):
	if (mark[i] == 0):
		topoSort(i)
topo.reverse()
for i in range(1, n+1):
	mark[i] = 0
dfs(s)
res = 0
for i in range(n):
	v = topo[i]
	if (mark[v] == 0):
		res += 1
		dfs(v)
#fou.write(str(res))
print(res)



from collections import defaultdict
import sys
def dfs(u):
    avail[u] = False
    for v in g[u]:
        if avail[v]:
            dfs(v)
    topo.append(u)


sys.setrecursionlimit(6000)
n, m, s = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)

avail, topo = [True] * n, []
for i,a in enumerate(avail):
    if a:
        dfs(i)
avail, res = [True] * n, 0
dfs(s - 1)
for i in reversed(topo):
    if avail[i]:
        res += 1
        dfs(i)
print(res)

import sys

n, m, s = list(map(int, input().split()))

adj = [[] for i in range(500005)]
ar = []
vis = [0 for i in range(500005)]
sys.setrecursionlimit(6000)

def dfs(s):
    vis[s] = 1
    for i in range(len(adj[s])):
        if(vis[adj[s][i]] == 0):
            dfs(adj[s][i])
    ar.append(s)


for i in range(m):
    u, v = list(map(int, input().split()))
    adj[u].append(v)

dfs(s)

for i in range(n):
    if(vis[i + 1] == 0):
        dfs(i + 1)
res = 0
vis = [0 for i in range(500005)]
for i in range(n - 1, -1, -1):
    if(vis[ar[i]] == 0):
        if(s != ar[i]):
            res += 1
        dfs(ar[i])

print(res)


import sys

n, m, s = list(map(int, input().split()))

adj = [[] for _ in range(500005)]
ar = []
vis = [0] * 500005
sys.setrecursionlimit(6000)

def dfs(s):
    vis[s] = 1
    for i in range(len(adj[s])):
        if(vis[adj[s][i]] == 0):
            dfs(adj[s][i])
    ar.append(s)


for i in range(m):
    u, v = list(map(int, input().split()))
    adj[u].append(v)

dfs(s)

for i in range(n):
    if(vis[i + 1] == 0):
        dfs(i + 1)
res = 0
vis = [0] * 500005
for i in range(n - 1, -1, -1):
    if(vis[ar[i]] == 0):
        if(s != ar[i]):
            res += 1
        dfs(ar[i])

print(res)


import sys

BigNum = 10 ** 10

class DSU:
    def __init__(self, count, stateInitializer, stateMerger):
        self.vs = list(range(count))
        self.states = [stateInitializer(i) for i in range(count)]
        self.sizes = [1] * count
        self.merger = stateMerger
    
    def get(self, i):
        if self.vs[i] == i:
            return i
        else:
            res = self.get(self.vs[i])
            self.vs[i] = res
            return res

    def getState(self, i):
        return self.states[self.get(i)]
    
    def setState(self, i, newState):
        i = self.get(i)
        self.states[i] = newState
    
    def unite(self, a, b):
        a = self.get(a)
        b = self.get(b)
        if a == b:
            return a

        mergedState = self.merger(self.states[a], self.states[b])
        if self.sizes[a] >= self.sizes[b]:
            self.vs[b] = a
            self.sizes[a] += self.sizes[b]
            self.states[a] = mergedState
            return a
        else:
            self.vs[a] = b
            self.sizes[b] += self.sizes[a]
            self.states[b] = mergedState
            return b
    
    def flatten(self):
        for i in range(len(self.vs)):
            self.get(i)
    
    def setNames(self):
        self.flatten()
        return set(self.vs)

n, m, s = list(map(int, input().split(' ')))
ps = [[] for _ in range(n+1)]
edges = []
for i in range(m):
    u, v = list(map(int, input().split(' ')))
    ps[v] += [u]
    edges += [(u, v)]

dsu = DSU(
    n+1,
    lambda i: (0, BigNum),
    lambda a, b: (min(a[0], b[0]), min(a[1], b[1]))
)

def dfs(v, depth):
    vSt = dsu.getState(v)
    vState, vMinDepth = vSt

    if vState >= 1:
        raise 'Not supposed to dfs processed node!'

    vState = 1
    vMinDepth = depth
    dsu.setState(v, (vState, vMinDepth))

    for nv in ps[v]:
        #print(':', v, nv)
        nvSt = dsu.getState(nv)
        nvState, nvMinDepth = nvSt

        if nvState == 2:
            continue
        if nvState == 1:
            if nvMinDepth < vMinDepth:
                vMinDepth = nvMinDepth
                dsu.setState(v, (vState, vMinDepth))
        else:
            nvMinDepth = dfs(nv, depth + 1)
            if nvMinDepth <= depth:
                dsu.unite(v, nv)

            if nvMinDepth < vMinDepth:
                vMinDepth = nvMinDepth
                dsu.setState(v, (vState, vMinDepth))

    if depth <= vMinDepth:
        vState = 2
        dsu.setState(v, (vState, vMinDepth))

    return vMinDepth


sys.setrecursionlimit(12000)

for i in range(1, n+1):
    st = dsu.getState(i)
    if st[0] == 0:
        dfs(i, 0)

components = dsu.setNames().difference({0})
#print(dsu.vs)
#print(components)

components = components.difference({ dsu.get(s) })
for (u, v) in edges:
    u, v = dsu.get(u), dsu.get(v)
    if u == v:
        continue
    components = components.difference({ v })

#print(components)
print(len(components))


import sys

BigNum = 10 ** 10

class DSU:
    def __init__(self, count, stateInitializer, stateMerger):
        self.vs = list(range(count))
        self.states = [stateInitializer(i) for i in range(count)]
        self.sizes = [1] * count
        self.merger = stateMerger
    
    def get(self, i):
        if self.vs[i] == i:
            return i
        else:
            res = self.get(self.vs[i])
            self.vs[i] = res
            return res

    def getState(self, i):
        return self.states[self.get(i)]
    
    def setState(self, i, newState):
        i = self.get(i)
        self.states[i] = newState
    
    def unite(self, a, b):
        a = self.get(a)
        b = self.get(b)
        if a == b:
            return a

        mergedState = self.merger(self.states[a], self.states[b])
        if self.sizes[a] >= self.sizes[b]:
            self.vs[b] = a
            self.sizes[a] += self.sizes[b]
            self.states[a] = mergedState
            return a
        else:
            self.vs[a] = b
            self.sizes[b] += self.sizes[a]
            self.states[b] = mergedState
            return b
    
    def flatten(self):
        for i in range(len(self.vs)):
            self.get(i)
    
    def setNames(self):
        self.flatten()
        return set(self.vs)

n, m, s = list(map(int, input().split(' ')))
ps = [[] for _ in range(n+1)]
edges = []
for i in range(m):
    u, v = list(map(int, input().split(' ')))
    ps[v] += [u]
    edges += [(u, v)]

dsu = DSU(
    n+1,
    lambda i: (0, BigNum),
    lambda a, b: (min(a[0], b[0]), min(a[1], b[1]))
)

def dfs(v, depth):
    vSt = dsu.getState(v)
    vState, vMinDepth = vSt

    if vState >= 1:
        raise 'Not supposed to dfs processed node!'

    vState = 1
    vMinDepth = depth
    dsu.setState(v, (vState, vMinDepth))

    for nv in ps[v]:
        #print(':', v, nv)
        nvSt = dsu.getState(nv)
        nvState, nvMinDepth = nvSt

        if nvState == 2:
            continue
        if nvState == 1:
            if nvMinDepth < vMinDepth:
                vMinDepth = nvMinDepth
                dsu.setState(v, (vState, vMinDepth))
        else:
            nvMinDepth = dfs(nv, depth + 1)
            if nvMinDepth <= depth:
                dsu.unite(v, nv)

            if nvMinDepth < vMinDepth:
                vMinDepth = nvMinDepth
                dsu.setState(v, (vState, vMinDepth))

    if depth <= vMinDepth:
        vState = 2
        dsu.setState(v, (vState, vMinDepth))

    return vMinDepth


sys.setrecursionlimit(6000)

for i in range(1, n+1):
    st = dsu.getState(i)
    if st[0] == 0:
        dfs(i, 0)

components = dsu.setNames().difference({0})
#print(dsu.vs)
#print(components)

components = components.difference({ dsu.get(s) })
for (u, v) in edges:
    u, v = dsu.get(u), dsu.get(v)
    if u == v:
        continue
    components = components.difference({ v })

#print(components)
print(len(components))


import sys


def d(u):
    rt[u] = False
    for v in q[u]:
        if rt[v]:
            d(v)
    topo.append(u)


sys.setrecursionlimit(6000)
n, m, s = map(int, input().split())
q = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    q[u - 1].append(v - 1)
rt, topo = [True] * n, []
for i,a in enumerate(rt):
    if a:
        d(i)
rt, res = [True] * n, 0
d(s - 1)
for i in reversed(topo):
    if rt[i]:
        res += 1
        d(i)
print(res)

import sys
sys.setrecursionlimit(6000)

n, m, s = map(int, input().split())
s -= 1
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a-1].append(b-1)

used = [False] * 5010
topo = []

def topo_sort(node):
    used[node] = True
    for c in g[node]:
        if not used[c]:
            topo_sort(c)
    topo.append(node)

def dfs(node):
    used[node] = True
    for c in g[node]:
        if not used[c]:
            dfs(c)

for i in range(n):
    if not used[i]:
        topo_sort(i)

topo.reverse()
for i in range(n):
    used[i] = False

dfs(s)
res = 0
for v in topo:
    if not used[v]:
        res += 1
        dfs(v)

print(res)

from collections import deque
import sys
sys.setrecursionlimit(1000000)
 

n, m, s = [int(x) for x in input().split()]
adj = [[] for u in range(n + 1)]
vis = [False for u in range(n + 1)]
for i in range(m):
    u, v = [int(x) for x in input().split()]
    adj[u].append(v)

def tarjan():
    low = [-1 for u in range(n + 1)]
    disc = [-1 for v in range(n + 1)]
    in_stack = [False for v in range(n + 1)]
    st = deque()
    comp = []

    def dfs(u):
        dfs.dfs_time = dfs.dfs_time + 1
        low[u] = dfs.dfs_time
        disc[u] = dfs.dfs_time
        in_stack[u] = True
        st.append(u)

        for v in adj[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif in_stack[v]:
                low[u] = min(low[u], disc[v])

        if low[u] == disc[u]:
            comp.append([])
            while u != st[-1]:
                x = st.pop()
                in_stack[x] = False
                comp[-1].append(x)
            x = st.pop()
            in_stack[x] = False
            comp[-1].append(x)

    dfs.dfs_time = 0
    for i in range(1, n + 1):
        if disc[i] == -1:
            dfs(i)

    return comp[::-1]

def visit(adj, vis, src):
    q = deque()
    q.append(src)
    vis[src] = True
    while len(q) > 0: 
        u = q.popleft()
        for v in adj[u]:
            if vis[v] == False:
                vis[v] = True
                q.append(v)
    
ans = 0
visit(adj, vis, s)
tarOrd = tarjan()
for lis in tarOrd:
    x = lis[0]
    if vis[lis[0]] == False:
        visit(adj, vis, x)
        ans += 1

print(ans)





from bisect import bisect
from collections import defaultdict
# l = list(map(int,input().split()))
# map(int,input().split()))
from math import gcd,sqrt,ceil
from collections import Counter
import sys
sys.setrecursionlimit(10**9)

def dfs(n):
    b[n] =True

    for i in hash[n]:
        if b[i] == False:
            dfs(i)

    top.append(n)
n,m,s = list(map(int,input().split()))

hash = defaultdict(list)

for i in range(m):
    a,b = list(map(int,input().split()))
    hash[a].append(b)

b = [False]*(n+1)
top = []
for i in range(1,n+1):
    if not b[i]:
        dfs(i)
b = [False]*(n+1)
dfs(s)
top.reverse()
count = 0
for i in top:
    if not b[i]:
        count+=1
        dfs(i)

print(count)



import sys
input = sys.stdin.readline

n, m, s = list(map(int, input().split()))
s -= 1
adj = [[] for _ in range(n)]
rev = [[] for _ in range(n)]

for u, v in (list(map(int, input().split())) for _ in range(m)):
    adj[u-1].append(v-1)
    rev[v-1].append(u-1)

group = [-1]*n
group[s] = 0
stack = [s]

while stack:
    v = stack.pop()
    for dest in adj[v]:
        if group[dest] != -1:
            continue
        group[dest] = 0
        stack.append(dest)

g = 0
for i in range(n):
    if group[i] != -1 or rev[i]:
        continue
    g += 1
    group[i] = g
    stack = [i]

    while stack:
        v = stack.pop()
        for dest in adj[v]:
            if group[dest] != -1:
                continue
            group[dest] = g
            stack.append(dest)

for i in range(n):
    if group[i] != -1:
        continue
    g += 1
    group[i] = g
    stack = [i]

    while stack:
        v = stack.pop()
        for dest in adj[v]:
            if group[dest] == 0 or group[dest] == g:
                continue
            group[dest] = g
            stack.append(dest)

print(len(set(group)) - 1)


import sys
input = sys.stdin.readline

n, m, s = list(map(int, input().split()))
s -= 1
adj = [[] for _ in range(n)]
rev = [[] for _ in range(n)]

for u, v in (list(map(int, input().split())) for _ in range(m)):
    adj[u-1].append(v-1)
    rev[v-1].append(u-1)

group = [-1]*n
g = 0
group[s] = g
stack = [s]

while stack:
    v = stack.pop()
    for dest in adj[v]:
        if group[dest] != -1:
            continue
        group[dest] = g
        stack.append(dest)


for i in range(n):
    if group[i] != -1:
        continue
    g += 1
    group[i] = g
    stack = [i]

    while stack:
        v = stack.pop()
        for dest in adj[v]:
            if group[dest] == 0 or group[dest] == g:
                continue
            group[dest] = g
            stack.append(dest)

print(len(set(group)) - 1)


# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(nodes, src):
    from collections import deque

    que = deque([(src, 0)])
    dist[src][src] = 1
    while que:
        u, c = que.popleft()
        for v in nodes[u]:
            if dist[src][v]:
                continue
            dist[src][v] = 1
            que.append((v, c+1))

N, M, s = MAP()
s -= 1

nodes = [[] for i in range(N)]
for _ in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)

dist = list2d(N, N, 0)
for i in range(N):
    bfs(nodes, i)

need = []
for v in range(N):
    if not dist[s][v]:
        need.append((dist[v].count(1), v))
need.sort(reverse=1)

done = [False] * N
ans = 0
for _, u in need:
    if not done[u]:
        for v, can in enumerate(dist[u]):
            if can:
                done[v] = True
        ans += 1
print(ans)


from collections import defaultdict

def topo_sort_variant(graph, n):
    result = []
    visited = [False] * (n+1)

    for i in range(1, n+1):
        if not visited[i]:
            stack = [i]
            while stack:
                node = stack[-1]
                if not visited[node]:
                    visited[node] = True
                    for child in graph[node]:
                        if not visited[child]:
                            stack.append(child)
                else:
                    result.append(stack.pop())
    return result



def __starting_point():
    min_roads_required = 0
    ncities, nroads, capital = map(int, input().split())

    g = defaultdict(list)

    for i in range(nroads):
        u, v = map(int, input().split())
        g[u].append(v)

    #print("The graph is:", g)
    op = topo_sort_variant(g, ncities)
    #print("The topo sort output is", op)

    visited = [False] * (ncities + 1)

    def topo_dfs(i):
        stack = [i]
        while stack:
            node = stack[-1]
            if not visited[node]:
                visited[node] = True
                for child in g[node]:
                    if not visited[child]:
                        stack.append(child)
            else:
                stack.pop()


    topo_dfs(capital)
    for i in reversed(topo_sort_variant(g, ncities)):
        if not visited[i]:
            topo_dfs(i)
            min_roads_required += 1

    print(min_roads_required)
__starting_point()

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)

def main():
    import sys
    sys.setrecursionlimit(10**5)
    from collections import deque
    n, m, s = map(int, input().split())
    s -= 1
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u-1].append(v-1)

    seen = [False]*n
    li = deque()

    def visit(node):
        if not seen[node]:
            seen[node] = True
            for c_node in graph[node]:
                visit(c_node)
            li.appendleft(node)

    def visit2(node):
        if not seen[node]:
            seen[node] = True
            for c_node in graph[node]:
                visit2(c_node)

    for i in range(n):
        visit(i)
    seen = [False]*n
    cnt = 0
    visit2(s)
    for i in li:
        if seen[i]:
            continue
        visit2(i)
        cnt += 1
    print(cnt)

def __starting_point():
    try:
        main()
    except:
        print('error!')
        return
__starting_point()

import sys
sys.setrecursionlimit(10**5)
from collections import deque
n, m, s = map(int, input().split())
s -= 1
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)

seen = [False]*n
li = deque()
def visit(node):
    if not seen[node]:
        seen[node] = True
        for c_node in graph[node]:
            visit(c_node)
        li.appendleft(node)
for i in range(n):
    visit(i)
seen = [False]*n
cnt = 0
li2 = list(li)
visit(s)
for i in li2:
    if seen[i]:
        continue
    visit(i)
    cnt += 1
print(cnt)