/*Kiem tra tinh lien thong giua hai dinh

Cho do thi vo huong G=(A,F) n dinh, m cung.Xet xem co duong di tu dinh S toi P hay ko?

Input: Tu Graph.inp co cau truc:

- Dong dau: n, m, s, p

- m dong sau: Moi dong 2 so nguyen duong (u,v) xac dinh cung (u,v)

Output: Ra Graph.out co cau truc:

- Co duong noi S va P ghi so 1 ra tep,nguoc lai ghi so 0.*/

//Thuat toan tim kiem theo chieu sau de quy (DFS)

#include<stdio.h>

#include<conio.h>

#define N 100

#define M 1000

int a[N][N];

int n,m,s,p;

int free[N];

int kt=0;

void input()

{

int i,j,u,v;

FILE *f;

f=fopen("Graph.inp","r");

if(f)

{

fscanf(f,"%d%d%d%d",&n,&m,&s,&p);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

a[i][j]=0;

for(i=1;i<=m;i++)

{ fscanf(f,"%d%d",&u,&v);

a[u][v]=1; a[v][u]=1;

}

for(i=1;i<=n;i++)

free[i]=1;

}

fclose(f);

}

void check(int u)

{

for(int v=1;v<=n;v++)

if(free[v]&&a[u][v])

{

free[v]=0;

check(v);

if(v==p) {kt=1;break;}

}

}

void output()

{FILE *f;

int i,j;

f=fopen("Graph.out","w+");

if(f)

{

if(kt) fprintf(f,"1");

else fprintf(f,"0");

}

fclose(f);

}

int main()

{

input();

check(s);

output();

puts("All completed!");

getch();

}