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.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Program10 {
    static Map<Integer, Set<Integer>> graph = new HashMap<>();
    static Map<Integer, Set<Integer>> inverted = new HashMap<>();
    static HashSet<Integer> reachable = new HashSet<>();
    private static Integer n;
    private static Integer m;
    private static Integer s;

    static void initGraphs(int n) {
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashSet<>());
            inverted.put(i, new HashSet<>());
        }
    }

    private static void add(Integer src, Integer dst) {
        graph.get(src).add(dst);
        inverted.get(dst).add(src);
    }

    private static void testInput() {
        n = 6;
        m = 4;
        s = 0;
        initGraphs(n);
        add(0, 1);
        add(2, 3);
        add(3, 4);
        add(5, 3);
    }

    private static void realInput() throws IOException {
        // TODO : минус 1 !
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        String firstLine = buffer.readLine();
        List<Integer> nums = Stream.of(firstLine.split(" ")).map(Integer::parseInt).collect(Collectors.toList());
        n = nums.get(0);
        m = nums.get(1);
        s = nums.get(2) - 1;
        initGraphs(n);
        for (int i = 0; i < m; i++) {
            String[] split = buffer.readLine().split(" ");
            int src = Integer.parseInt(split[0]) - 1;
            int dst = Integer.parseInt(split[1]) - 1;
            add(src, dst);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        realInput();
//        testInput();

        fillReachable(s);
        List<Integer> ordered = topoSort(graph);
        Collections.reverse(ordered);
        int cnt = 0;
        for (Integer v : ordered) {
            if (!reachable.contains(v)) {
                //System.out.println((s + 1) + " " + (v + 1));
                cnt++;
                fillReachable(v);
            }
        }
        System.out.println(cnt);
    }

    private static void fillReachable(int v) {
        reachable.add(v);
        for (Integer vv : graph.get(v)) {
            if (!reachable.contains(vv)) {
                fillReachable(vv);
            }
        }
    }

    private static List<Integer> topoSort(Map<Integer, Set<Integer>> graph) {
        HashSet<Integer> visited = new HashSet<>();
        List<Integer> ordered = new ArrayList<>();
        for (Integer i : graph.keySet()) {
            if (visited.contains(i)) {
                continue;
            }
            dfs1(graph, visited, ordered, i);
        }
        return ordered;
    }

    private static void dfs1(Map<Integer, Set<Integer>> graph, HashSet<Integer> visited,
            List<Integer> ordered, int v)
    {
        visited.add(v);
        if (graph.containsKey(v)) {
            for (Integer vv : graph.get(v)) {
                if (visited.contains(vv)) {
                    continue;
                }
                dfs1(graph, visited, ordered, vv);
            }
        }
        ordered.add(v);
    }
}
