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

public class Main {
    public static void main(String[] args) throws Exception {
        new Solver().run(1);
    }
}

class Solver {

    private BufferedReader reader = null;
    private StringTokenizer st = null;

    private int n, m, s;
    private List<List<Integer>> graph;
    private boolean[] inTree, used;
    private ArrayList<Pair> weight;
    private Queue<Integer> queue;

    private int ans = 0;

    public void run(int inputType) throws Exception {
        if (inputType == 0)
            reader = new BufferedReader(new FileReader("input.txt"));
        else
            reader = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken()) - 1;

        inTree = new boolean[n];
        used = new boolean[n];
        weight = new ArrayList<>(n);
        graph = new ArrayList<>(n);
        queue = new LinkedList<>();

        for (int i = 0; i < n; ++i) {
            graph.add(new LinkedList<>());
        }

        for (int i = 0; i < m; ++i) {


            st = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            graph.get(x).add(y);
        }

        reader.close();

        bfsMarkInTree(s);

        for (int i = 0; i < n; ++i) {
            if (inTree[i])
                continue;

            Arrays.fill(used, false);
            queue.clear();
            weight.add(new Pair(i, bfsCalcWeight(i)));
        }

        Collections.sort(weight);

        for (Pair p : weight) {
            if (inTree[p.x])
                continue;

            bfsMarkInTree(p.x);
            ans++;
        }

        System.out.println(ans);
    }

    void bfsMarkInTree(int v) {

        queue.offer(v);
        inTree[v] = true;

        while(queue.size() > 0) {

            int u = queue.poll();

            for (Integer t : graph.get(u)) {
                if (inTree[t])
                    continue;

                inTree[t] = true;
                queue.offer(t);
            }
        }
    }

    int bfsCalcWeight(int v) {

        used[v] = true;
        int amount = 1;
        queue.offer(v);

        while(queue.size() > 0) {

            int u = queue.poll();

            for (Integer t : graph.get(u)) {

                if (used[t] || inTree[t])
                    continue;

                used[t] = true;
                amount++;
                queue.offer(t);
            }
        }

        return amount;
    }

    class Pair implements Comparable<Pair> {
        int x;
        int y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pair o) {
            return o.y - y;
        }

        @Override
        public String toString() {
            return "{" + x + ", " + y + "}";
        }
    }
}
