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.lang.reflect.Array;
import java.util.*;
import java.util.regex.Pattern;

public class S {
    static int count=0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t=1;
        while(t--!=0){
           int n=sc.nextInt();
           int m=sc.nextInt();
           int s=sc.nextInt();
           LinkedList<Integer> l[]=new LinkedList[n+1];
           for(int i=0;i<n+1;i++) l[i]=new LinkedList<>();
           for(int i=0;i<m;i++){
               int u=sc.nextInt();
               int v=sc.nextInt();
               l[u].add(v);
           }
           ArrayList<Integer> str=new ArrayList<>();
           int visited[]=new int[n+1];
           visited[0]=1;
           dfs(s,l,str,visited);
            ArrayList<Integer> s1=new ArrayList<>();
           for(int i=0;i<n+1;i++){
               if(visited[i]==0) s1.add(i);
           }
            ArrayList<store> list=new ArrayList<>();
            for(int src:s1){
                int v[]=new int[n+1];
                count=0;
                dfs1(src,l,s1,v,visited);
                list.add(new store(src,count));
            }

//            Comparator<store> com=new Comparator<store>() {
//                @Override
//                public int compare(store o1, store o2) {
//                    return o1.c<o2.c?1:-1;
//                }
//            };
//            Comparator<store> com=new Comparator<store>() {
//                @Override
//                public int compare(store o1, store o2) {
//                    if(o1.c<o2.c) return 1;
//                    if(o1.c>o2.c) return -1;
//
//                    long t=Double.doubleToLongBits(o1.c);
//                    long t2=Double.doubleToLongBits(o2.c);
//                    return (t==t2 ? 0:(t<t2 ? -1:1)); }
//            };
            Collections.sort(list,(o1,o2)->o2.c-o1.c);
            int res=0;
            for(store i:list){
                if(visited[i.src]==0){
                    res++;
                    int v[]=new int[n+1];
                    dfs2(i.src,l,v,visited);
                }
            }
//            for(int i=1;i<n+1;i++){
//                if(visited[i]==0) res++;
//            }
            System.out.println(res);
        }
    }

    public static void dfs2(int s,LinkedList<Integer> l[],int v[],int visited[]){
        v[s]=1;
        Iterator<Integer> it=l[s].iterator();
        while(it.hasNext()){
            int n=it.next();
            if(v[n]==0){
                if(visited[n]==0) visited[n]=1;
                dfs2(n,l,v,visited);
            }
        }
    }

    public static void dfs1(int s,LinkedList<Integer> l[],ArrayList<Integer> str,int v[],int visited[]){
        v[s]=1;
        Iterator<Integer> it=l[s].iterator();
        while(it.hasNext()){
            int n=it.next();
            if(v[n]==0){
                if(visited[n]==0) count++;
                dfs1(n,l,str,v,visited);
            }
        }
    }
    public static void dfs(int s,LinkedList<Integer> l[],ArrayList<Integer> str,int visited[]){
        visited[s]=1;
        Iterator<Integer> it=l[s].iterator();
        while(it.hasNext()){
            int n=it.next();
            if(visited[n]==0) dfs(n,l,str,visited);
        }
    }
}
class store{
    int src,c;
    public store(int src,int c){
        this.src=src;
        this.c=c;
    }
}

