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 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class CF999E {
    public static void main(String[] args) throws IOException {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        int n = sc.nextInt(), m = sc.nextInt(), s = sc.nextInt() - 1;
        DirectedGraph g = new DirectedGraph(n);
        while (m-- > 0)
            g.addEdge(sc.nextInt() - 1, sc.nextInt() - 1);

        ArrayList<Integer> unreachable = g.bfsUnreachable(s);
        int[] bfsCnt = new int[n];
        for (int v : unreachable)
            bfsCnt[v] = g.bfsCnt(v);
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((v1, v2) -> bfsCnt[v2] - bfsCnt[v1]);
        for (int v : unreachable)
            pq.add(v);

        int edges = 0;
        boolean[] visited = new boolean[n];
        while (!pq.isEmpty()) {
            int v = pq.poll();
            if (!visited[v]) {
                edges++;
                g.bfsMark(v, visited);
            }
        }
        pw.println(edges);
        pw.flush();
    }

    static class DirectedGraph {
        ArrayList<Integer>[] adjList;
        int n;

        DirectedGraph(int n) {
            this.n = n;
            adjList = new ArrayList[n];
            Arrays.setAll(adjList, i -> new ArrayList<Integer>());
        }

        void addEdge(int v, int w) {
            adjList[v].add(w);
        }

        ArrayList<Integer> bfsUnreachable(int s) {
            Queue<Integer> q = new LinkedList<Integer>();
            boolean[] reachable = new boolean[n];
            q.add(s);
            reachable[s] = true;
            while (!q.isEmpty()) {
                int v = q.poll();
                for (int w : adjList[v]) {
                    if (!reachable[w]) {
                        q.add(w);
                        reachable[w] = true;
                    }
                }
            }
            ArrayList<Integer> unreachable = new ArrayList<>(n);
            for (int i = 0; i < n; i++)
                if (!reachable[i])
                    unreachable.add(i);
            return unreachable;
        }

        int bfsCnt(int s) {
            Queue<Integer> q = new LinkedList<Integer>();
            boolean[] visited = new boolean[n];
            q.add(s);
            visited[s] = true;
            int cnt = 0;
            while (!q.isEmpty()) {
                for (int w : adjList[q.poll()])
                    if (!visited[w]) {
                        q.add(w);
                        visited[w] = true;
                        cnt++;
                    }
            }
            return cnt;
        }

        void bfsMark(int s, boolean[] visited) {
            Queue<Integer> q = new LinkedList<Integer>();
            q.add(s);
            visited[s] = true;
            while (!q.isEmpty()) {
                for (int w : adjList[q.poll()])
                    if (!visited[w]) {
                        q.add(w);
                        visited[w] = true;
                    }
            }
        }
    }

    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;

        public FastScanner() {
            this.in = new BufferedReader(new InputStreamReader(System.in));
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        public void close() throws IOException {
            in.close();
        }
    }
}