欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 999 - E. Reachability from the Capital(trajan+缩点)

程序员文章站 2022-05-15 14:01:58
...

E. Reachability from the Capital

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 vvto 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

Copy

9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1

output

Copy

3

input

Copy

5 4 5
1 2
2 3
3 4
4 1

output

Copy

1

Note

The first example is illustrated by the following:

Codeforces 999 - E. Reachability from the Capital(trajan+缩点)

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:

Codeforces 999 - E. Reachability from the Capital(trajan+缩点)

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.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define LL long long

const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const int N = 10010;

int n,m,s;
int tot,num,temp;
int dfn[N],low[N],color[N],vis[N],in[N];
vector<int>G[N];
stack<int>S;
void init(){
    tot = num = temp = 0;
    while(!S.empty())   S.pop();
    for(int i=0;i<=n;i++){
        G[i].clear();
    }
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    memset(low,0,sizeof(low));
    memset(in,0,sizeof(in));
    memset(color,0,sizeof(color));
}
void tarjan(int x){
    low[x] = dfn[x] = ++ tot;
    S.push(x);
    vis[x] = 1;
    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(vis[v])
            low[x] = min(low[x],dfn[v]);
    }
    if(dfn[x] == low[x]){
        num++;
        while(1){
            int now = S.top();
            S.pop();
            color[now] = num;
            vis[now] = 0;
            if(now == x)    break;
        }
    }
}
void Build(){
    for(int i=1;i<=n;i++){
        for(int j=0;j<G[i].size();j++){
            int v = G[i][j];
            if(color[v] != color[i]){
                in[color[v]] ++;
            }
        }
    }
    for(int i=1;i<=num;i++){
        if(in[i]==0){
            temp ++;
        }
    }
}
int main(){
    while(scanf("%d%d%d",&n,&m,&s)!=EOF){
        init();
        int u,v;
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]) tarjan(i);
        }
        Build();
        if(in[color[s]]==0) temp--;
        cout<<temp<<endl;
    }
    return 0;
}