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

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 = map(int, input().split(' '))
ps = [[] for _ in range(n+1)]
edges = []
for i in range(m):
    u, v = 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))
