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

public class Main {
	static final long MOD = 998244353;
	static boolean[] visited;
	static boolean[] visitedBad;
    public static void main(String[] args) throws IOException {
        FastScanner sc=new FastScanner();
        int N = sc.nextInt();
        int M = sc.nextInt();
        int capital = sc.nextInt()-1;
        visited = new boolean[N];
        visitedBad = new boolean[N];
        Node[] nodes = new Node[N];
        for (int i = 0; i < N; i++)
        	nodes[i] = new Node(i);
        for (int i = 0; i < M; i++) {
        	int s = sc.nextInt()-1;
        	int e = sc.nextInt()-1;
        	nodes[s].addChild(nodes[e]);
        }
        int visits = DFSRoadBuilding(nodes[capital]);
        int[][] badNodes = new int[5000][2];
        for (int i = 0; i < N; i++) {
        	if (! visited[i]) {
        		//This node can't be directly accessed from the capital.
        		//Check how many other "bad" nodes it can get.
        		int bad = DFSBad(nodes[i],N);
        		badNodes[i][0] = i;
        		badNodes[i][1] = bad;
        	}
        }
        Arrays.sort(badNodes, new Comparator<int[]>() {
        	  @Override
        	  public int compare(int[] arr1, int[] arr2) {
        	    return arr2[1]-arr1[1];
        	  }
        });
        int answer = 0;
        int index = 0;
        while (visits < N) {
        	if (visited[badNodes[index][0]]) {
        		index++;
        		continue;
        	}
        	answer++;
        	visits += DFSRoadBuilding(nodes[badNodes[index][0]]);
        	index++;
        }
        System.out.println(answer);
    }
    
    public static int DFSRoadBuilding(Node root) {
    	int newVisits = 0;
    	//Initialize Stack
        Stack<Node> s = new Stack<Node>();
        visited[root.n] = true;
        s.push(root);
        
        //Loop through DFS Algorithm
        while (s.isEmpty() == false) {
        	Node parent = s.pop();
        	newVisits++;
        	for (Node child: parent.children) {
        		if (! visited[child.n]) {
        			visited[child.n] = true;
        			s.push(child);
        		}
        	}
    	}
        return newVisits;
    }
    
    public static int DFSBad(Node root, int N) {
    	if (visitedBad[root.n]) return 0;
    	//Initialize Stack
        Stack<Node> s = new Stack<Node>();
        visitedBad[root.n] = true;
        boolean[] tempVis = new boolean[N];
        tempVis[root.n] = true;
        s.push(root);
        int bad = 0;
        //Loop through DFS Algorithm
        while (s.isEmpty() == false) {
        	Node parent = s.pop();
        	bad++;
        	for (Node child: parent.children) {
        		if ((! visited[child.n]) && (! tempVis[child.n])) {
        			visitedBad[child.n] = true;
        			tempVis[child.n] = true;
        			s.push(child);
        		}
        	}
    	}
        return bad;
    }
    
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
}

class Node {
	public int n;
	public HashSet<Node> children;
	
	public Node(int n) {
		this.n = n;
		children = new HashSet<Node>();
	}
	
	public void addChild(Node node) {
		children.add(node);
	}
	
	public void removeChild(Node node) {
		children.remove(node);
	}
}

class BinaryIndexedTree {
	  public long[] arr;

	  public BinaryIndexedTree (int N) {
	    arr = new long[N+1];
	    arr[0] = 0;
	  }

	  //add k to the i-th element.
	  public void add(long k, int i) {
	    int node = i+1;
	    while (node < arr.length) {
	      arr[node] += k;
	      node += node & (-node);
	    }
	  }

	  //sum up the elements from input[s_i] to input[e_i], from [s_i,e_i).
	  public long sum(int s_i, int e_i) {
	    return sum(e_i) - sum(s_i);
	  }

	  public long sum(int i) {
	    long total = 0;
	    int node = i;
	    while (node > 0) {
	      total += arr[node];
	      node -= node & (-node);
	    }
	    return total;
	  }
}