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.Stack;
import java.util.StringTokenizer;

public class CF999E_1 {
    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;
        Graph g = new Graph(n);
        while (m-- > 0)
            g.addEdge(sc.nextInt() - 1, sc.nextInt() - 1);

        int[] sccIdx = g.findSCCs();

        int[] indeg = new int[g.sccCnt];
        for (int v = 0; v < n; v++)
            for (int w : g.adjList[v])
                if (sccIdx[v] != sccIdx[w])
                    indeg[sccIdx[w]] += 1;

        int edges = 0;
        for (int i = 0; i < indeg.length; i++)
            if (indeg[i] == 0 && i != sccIdx[s])
                edges++;

        pw.println(edges);
        pw.flush();
    }

    static class Graph {
        ArrayList<Integer>[] adjList;
        ArrayList<Integer>[] reverseAdjList;
        int[] sccIdx;
        int sccCnt;
        int n;

        @SuppressWarnings("unchecked")
        Graph(int n) {
            this.n = n;
            adjList = new ArrayList[n];
            Arrays.setAll(adjList, i -> new ArrayList<Integer>());
            reverseAdjList = new ArrayList[n];
            Arrays.setAll(reverseAdjList, i -> new ArrayList<Integer>());
            sccIdx = new int[n];
        }

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

        int[] findSCCs() {
            Stack<Integer> s = topologicalSort();
            boolean[] visited = new boolean[n];
            int idx = 0;
            while (!s.isEmpty()) {
                int v = s.pop();
                if (!visited[v])
                    reverseDFS(v, idx++, visited);
            }
            this.sccCnt = idx;
            return sccIdx;
        }

        Stack<Integer> topologicalSort() {
            Stack<Integer> s = new Stack<Integer>();
            boolean[] visited = new boolean[n];
            for (int i = 0; i < n; i++)
                if (!visited[i])
                    topologicalSortUtil(i, s, visited);
            return s;
        }

        private void topologicalSortUtil(int v, Stack<Integer> s, boolean[] visited) {
            visited[v] = true;
            for (int w : adjList[v])
                if (!visited[w])
                    topologicalSortUtil(w, s, visited);
            s.push(v);
        }

        private void reverseDFS(int v, int idx, boolean[] visited) {
            visited[v] = true;
            sccIdx[v] = idx;
            for (int w : reverseAdjList[v])
                if (!visited[w])
                    reverseDFS(w, idx, visited);
        }
    }

    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();
        }
    }
}