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

public class ProblemE {

    public static InputStream inputStream = System.in;

    public static OutputStream outputStream = System.out;

    public static void main(String[] args) {
        MyScanner scanner = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int c = scanner.nextInt();

        Graph graph = new Graph(n);
        for (int i = 0; i < m; i++) {
            graph.addEdge(scanner.nextInt(), scanner.nextInt());
        }

        out.print(graph.solve(c));


        out.flush();
    }

    private static class Graph {

        private Map<Integer, Node> nodes = new HashMap<>();

        private Graph(int n) {
            for (int i = 1; i <= n; i++) {
                nodes.put(i, new Node(i));
            }
        }

        private void addEdge(int x, int y) {
            nodes.get(x).adjacents.add(nodes.get(y));
        }

        private int solve(int c) {
            Node root = nodes.get(c);
            LinkedList<Node> toVisit = new LinkedList<>();
            root.visited = true;
            toVisit.add(root);
            while (!toVisit.isEmpty()) {
                Node node = toVisit.poll();
                for (Node adjacent : node.adjacents) {
                    if (!adjacent.visited) {
                        adjacent.visited = true;
                        toVisit.add(adjacent);
                    }
                }
            }

            List<Pair<Integer, Integer>> pairs = new ArrayList<>();
            boolean[] visits = new boolean[nodes.size() + 1];
            for (Node node : nodes.values()) {
                visits[node.label] = node.visited;
            }

            for (Node r : nodes.values()) {
                if (!r.visited) {
                    int x = 0;
                    toVisit = new LinkedList<>();
                    r.visited = true;
                    toVisit.add(r);
                    while (!toVisit.isEmpty()) {
                        Node node = toVisit.poll();
                        x++;
                        for (Node adjacent : node.adjacents) {
                            if (!adjacent.visited) {
                                adjacent.visited = true;
                                toVisit.add(adjacent);
                            }
                        }
                    }
                    pairs.add(new Pair<>(x, r.label));

                    for (int j = 1; j <= nodes.size(); j++) {
                        nodes.get(j).visited = visits[j];
                    }
                }
            }

            Collections.sort(pairs, (a, b) -> Integer.compare(b.first, a.first));

            int ans = 0;
            for (Pair<Integer, Integer> pair : pairs) {
                Node r = nodes.get(pair.second);
                if (!r.visited) {
                    ans++;
                    toVisit = new LinkedList<>();
                    r.visited = true;
                    toVisit.add(r);
                    while (!toVisit.isEmpty()) {
                        Node node = toVisit.poll();
                        for (Node adjacent : node.adjacents) {
                            if (!adjacent.visited) {
                                adjacent.visited = true;
                                toVisit.add(adjacent);
                            }
                        }
                    }
                }
            }


            return ans;
        }
    }

    private static class Node {

        private int label;

        private boolean visited;

        private List<Node> adjacents = new ArrayList<>();

        private Node(int label){
            this.label = label;
        }
    }

    private static class MyScanner {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        private MyScanner(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        }

        private String next() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        private int nextInt() {
            return Integer.parseInt(next());
        }

        private long nextLong() {
            return Long.parseLong(next());
        }

        private double nextDouble() {
            return Double.parseDouble(next());
        }

        private String nextLine() {
            String str = "";
            try {
                str = bufferedReader.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    private static class Pair<F, S> {

        private F first;

        private S second;

        public Pair() {}

        public Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }
    }

    private static class Triple<F, S, T> {

        private F first;

        private S second;

        private T third;

        public Triple() {}

        public Triple(F first, S second, T third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }
    }
}
