题目描述

There are $\mathrm{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 $\mathrm{nn, mm and ss (1\le n\le 5000,0\le m\le 5000,1\le s\le n1\le n\le 5000,0\le m\le 5000,1\le s\le n)\; —\; the\; number\; of\; cities,\; the\; number\; of\; roads\; and\; the\; index\; of\; the\; capital.\; Cities\; are\; indexed\; from 11 to nn.}$

The following $\mathrm{mm lines\; contain\; roads:\; road ii is\; given\; as\; a\; pair\; of\; cities uiui, vivi (1\le ui,vi\le n1\le ui,vi\le n, ui\ne viui\ne 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 $\mathrm{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

 

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.

 

题解： 

强连通缩点后统计入度为0的个数ans，然后看首都的入度是否为0；如果是则ans-1;

1 #include
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 using namespace std; 7  8 const int MAXN=1e5+10; 9 const int inf=0x3f3f3f3f;10 struct node{11     int to;12     int next;13 }edge[MAXN*4];14 int head[MAXN];15 int val[MAXN];16 bool instack[MAXN];17 int cnt;18 int dfn[MAXN],low[MAXN];19 int sum[MAXN];20 void add(int x,int y)21 {22     edge[++cnt].to =y;23     edge[cnt].next=head[x];24     head[x]=cnt;25 }26 int Time,num;27 stack
            
             st;28 int du[MAXN];29 int color[MAXN];30 int x[MAXN],y[MAXN];31 void tarjan(int u)32 {33 dfn[u]=low[u]= ++Time;34 st.push(u);35 instack[u]=true;36 for (int i = head[u]; i !=-1 ; i=edge[i].next) {37 int v=edge[i].to;38 if(!dfn[v]){39 tarjan(v);40 low[u]=min(low[u],low[v]);41 }42 else if(instack[v]) low[u]=min(low[u],dfn[v]);43 }44 if(dfn[u]==low[u])45 {46 int x;47 num++;48 while(1) {49 x=st.top();50 st.pop();51 color[x]=num;52 instack[x]=false;53 if(x==u) break;54 }55 56 }57 }58 59 int main()60 {61 int n,m,s;62 scanf("%d%d%d",&n,&m,&s);63 cnt=0;64 memset(head,-1,sizeof(head));65 memset(instack,false, sizeof(instack));66 memset(sum, 0,sizeof(sum));67 for (int i = 1; i <=m ; ++i) {68 scanf("%d%d",&x[i],&y[i]);69 add(x[i],y[i]);70 }71 for (int i = 1; i <=n ; ++i) {72 if(!dfn[i]) tarjan(i);73 }74 for (int i = 1; i <=m ; ++i) {75 if(color[x[i]]!=color[y[i]])76 {77 du[color[y[i]]]++;78 }79 }80 81 int ans=0;82 for (int i = 1; i <=num ; ++i) {83 if(du[i]==0) ans++;84 }85 if(du[color[s]]==0) ans--;86 printf("%d\n",ans);87 return 0;88 }