Reachability from the Capital

There are nn cities and mm 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 nn, mm and ss (1≤n≤5000,0≤m≤5000,1≤s≤n1≤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 11 to nn.

The following mm lines contain roads: road ii is given as a pair of cities uiui, vivi (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi). For each pair of cities (u,v)(u,v), there can be at most one road from uu to vv. Roads in opposite directions between a pair of cities are allowed (i.e. from uu to vv and from vv to uu).

Output

Print one integer — the minimum number of extra roads needed to make all the cities reachable from city ss. If all the cities are already reachable from ss, 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:

For example, you can add roads (6,46,4), (7,97,9), (1,71,7) to make all the cities reachable from s=1s=1.

The second example is illustrated by the following:

In this example, you can add any one of the roads (5,15,1), (5,25,2), (5,35,3), (5,45,4) to make all the cities reachable from s=5s=5.

---

写这题之前不会tarjan..是一直看不懂网上的讲解。然后补题的时候看了个视频懂了。如果大家想学tarjan或者理解的话可以去b站上搜下tarjan：[算法]轻松掌握tarjan强连通分量_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili（我真的是看完就懂了

所以这题就是加个缩点的板子题了。

什么是缩点呢？就是把一个环变成点，每个环有一个新的编号，然后缩完点之后就达到了简化的目的。

缩点要找环，把每一个环变成同一个编号的新点，然后建一张新图去写题。

缩完点后这题就变成了一个关于度数的题。有向环上的任意一个点都可以到环上的其他点，然后这个环如果有到其他环的边，就可以去另外的环上，到达另外环上的任意一个点。

所以这题看缩点后s所在的点在哪，不管是孤立点还是在里面缩点的任意一个点，剩下要找的就是几个入度为0且没被访问的点了（这个画图分析感觉出来的）

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5;
typedef long long LL;
int dfn[maxn],low[maxn],time,n,m,x,y,start;
bool inq[maxn];
vector <int> g[maxn];
stack <int> s;
int col[maxn],cnt=0,in[maxn];//缩点 
void tarjan(int x){
    dfn[x] = low[x] = ++time;
    s.push(x);inq[x] = true;

    for (int i=0;i<g[x].size();i++){
        int v = g[x][i];
        if (!dfn[v]){
            tarjan(v);
            low[x] = min(low[x],low[v]);
        }else if (inq[v])
            low[x] = min(low[x],dfn[v]);
    }
    
    if (low[x] == dfn[x]){
        cnt++;//缩点 
        int y;//放外面 
        do{
            y = s.top();
            inq[y] = false;
			col[y]=cnt;
            s.pop();
        }while (y != x);
    
        return;
    }
}

int main(){
    cin>>n>>m>>start;
    for (int i=1;i<=m;i++){
        cin>>x>>y;
        g[x].push_back(y);
    }

    for (int i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i);
  	for(int i=1;i<=n;i++){
  		for(int j=0;j<g[i].size();j++){
  			int u=col[i];
  			int to=col[g[i][j]];
  			if(u!=to) in[to]++;
		}
	}
	int sum=0;
	for(int i=1;i<=cnt;i++){
		if(i!=col[start]&&in[i]==0) sum++;//s的缩点连通块和其他不在同一个联通块并且其他连通块的入度为0 
	}
	cout<<sum<<endl; 
    return 0;
}