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 Codeforces
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        String s[]=bu.readLine().split(" ");
        int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]),c=Integer.parseInt(s[2]),i,ans=0;

        ArrayList<Integer> g[]=new ArrayList[n+1];
        for(i=0;i<=n;i++)
        g[i]=new ArrayList<>();
        for(i=0;i<m;i++)
        {
            s=bu.readLine().split(" ");
            int u=Integer.parseInt(s[0]),v=Integer.parseInt(s[1]);
            g[u].add(v);
        }
        vis=new boolean[n+1];
        ans=0;
        dfs(g,c,vis,0);

        ArrayList<Pair> al=new ArrayList<>();
        for(i=1;i<=n;i++)
        if(!vis[i])
        al.add(new Pair(dfs(g,i,new boolean[n+1],1),i));

        Collections.sort(al, new Comparator<Pair>() {
            public int compare(Pair o1, Pair o2) {
                if(o1.d<o2.d) return 1;
                else if(o1.d==o2.d) return o1.i>o2.i?1:-1;
                else return -1;
            }});

        for(i=0;i<al.size();i++)
        if(!vis[al.get(i).i])
        {
            ans++;
            dfs(g,al.get(i).i,vis,0);
        }
        System.out.print(ans);
    }

    static boolean vis[];
    static class Pair
    {
        int d,i;
        Pair(int a,int b)
        {
            d=a;
            i=b;
        }
    }

    static int dfs(ArrayList<Integer> g[],int c,boolean v[],int k)
    {
        Stack<Integer> s=new Stack<>();
        s.add(c);
        if(k==0) vis[c]=true;
        else v[c]=true;
        int a=1;
        while(!s.isEmpty())
        {
            int p=s.pop();
            for(int x:g[p])
            if(k==0)
            {
                if(!vis[x])
                {
                    vis[x]=true;
                    a++;
                    s.add(x);
                }
            }
            else
            {
                if(!vis[x] && !v[x])
                {
                    v[x]=true;
                    s.add(x);
                    a++;
                }
            }
        }
        return a;
    }
}