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.*;

/**
 *
 * @author user
 */
public class Graph {

    /**
     * @param args the command line arguments
     */
    static class point implements Comparable<point> {
        int num ;
        int count ;
        point(int num, int count){
            this.num = num ;
            this.count = count ;
        }

        @Override
        public int compareTo(point b) {
             return this.count < b.count ? 1:(this.count == b.count ? 0:-1) ; 
        }
    }
    
    static void dfsFirst(int node, int k, int[] group,Vector[] v){
        group[node] = k;
        for(int i=0;i<v[node].size();i++){
            int next = (int) v[node].get(i) ;
            if(group[next] == -1){
                dfsFirst(next, k, group, v) ;
            }
        }
    }
    
    static int dfs(int node,boolean[] used,int[] group,Vector[] v){
        used[node] = true ;
        int count = 1 ;
        for(int i=0;i<v[node].size();i++){
            int next = (int) v[node].get(i) ;
            if(group[next] != 0 && !used[next]){
                count += dfs(next,used,group,v) ;
            }
        }
        return count ;
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
         Scanner in = new Scanner(System.in) ;
       int n = in.nextInt() ;
       int m = in.nextInt() ;
       int s = in.nextInt() -1;
       int[] group = new int[n] ;
       boolean[] used = new boolean[n] ;
       PriorityQueue<point> Q = new PriorityQueue<point>() ;
       
       Arrays.fill(group, -1);
       int cur = 1 ;
       
       Vector[] v = new Vector[n] ;
       
       for(int i=0;i<n;i++){
           v[i] = new Vector<Integer>() ;
       }
       
       for(int i=0;i<m;i++){
           int from = in.nextInt() -1 ;
           int to   = in.nextInt() -1 ;
           v[from].add(to) ;
       }
       
       dfsFirst(s, 0, group, v) ;
       
       for(int i=0;i<n;i++){
           if(group[i] != 0){
               Arrays.fill(used, false);
               Q.add(new point(i, dfs(i, used, group, v))) ;
           }
       }
       
       int count = 0 ;
              
       while(!Q.isEmpty()){
           point p =Q.poll() ;
           if(group[p.num] == 0) continue ;
           
           dfsFirst(p.num, 0, group, v) ;
           count++;
           
       }
       
       System.out.println(count) ;
    }
    
}