#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
struct nod{
int nr;
nod * ante;
};
nod *p, *l[50];
int i,j,k,n,nrarc,m[50][50],c[50],v[50],ic,sc;
char numefis[20];
void bf(){
nod *q;
while(ic<=sc){
q=l[c[ic]];
while(q){
if(!v[q->nr]){
sc++;
c[sc]=q->nr;
v[q->nr]=1;
}
q=q->ante;
}
ic++;
bf();
}
}
void bfm(){
int q;
while(ic<=sc){
for(q=k;q<=n;q++)
if((!v[q])&&(m[c[ic]][q])){
sc++;
c[sc]=q;
v[q]=1;
}
ic++;
bfm();
}
}
void df(int k){
nod *q;
cout<<k<<" ";
q=l[k];
v[k]=1;
while(q){
if(!v[q->nr])df(q->nr);
q=q->ante;
}
}
void dfm(int k){
int q;
cout<<k<<" ";
v[k]=1;
for(q=1;q<=n;q++)
if((!v[q])&&(m[k][q]))dfm(q);
}
int main()
{
// cout<<"numele fisierului de intrare ?";
// cin>>numefis;
// cout<<endl;
// ifstream f(numefis);
cin>>n;cin>>nrarc;
cout<<"sunt "<<n<<" noduri si "<<nrarc<<" arce"<<endl;
for(k=1;k<=nrarc;k++)l[k]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
m[i][j]=0;
for(k=1;k<=nrarc;k++){
cin>>i;
cin>>j;
m[i][j]=1;
m[j][i]=1;
cout<<k<<" : arc de la "<<i<<" la "<<j<<endl;
p=new nod;p->nr=j;p->ante=l[i];l[i]=p;
p=new nod;p->nr=i;p->ante=l[j];l[j]=p;
}
cout<<endl<<"matricea adiacentelor :"<<endl<<endl;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)cout<<m[i][j]<<" ";
cout<<endl;
}
// f.close();
cout<<endl<<"listele de adiacenta :"<<endl<<endl;
for(i=1;i<=n;i++){
cout<<i<<" ";
p=l[i];
while(p){
cout<<p->nr<<" ";
p=p->ante;
}
cout<<endl;
}
cout<<endl<<"strabaterea in latime (cazul listelor de adiacenta) :"<<endl;
cout<<"nodul de inceput : ";
cin>>k; cout<<k<<endl;
ic=1;
sc=1;
c[ic]=k;
v[k]=1;
bf();
cout<<endl;
for(i=1;i<=sc;i++)cout<<c[i]<<" ";
cout<<endl<<endl<<"strabaterea in latime (cazul matricei de adiacenta) :"<<endl;
cout<<"nodul de inceput : ";
cin>>k; cout<<k<<endl;
bfm();
cout<<endl;
for(i=1;i<=sc;i++)cout<<c[i]<<" ";
cout<<endl<<endl<<"strabaterea in adancime (cazul listelor de adiacenta) :"<<endl;
cout<<"nodul de inceput :";
cin>>k; cout<<k<<endl;
cout<<endl;
for(i=1;i<=n;i++)v[i]=0;
df(k);
cout<<endl<<endl<<"strabaterea in adancime (cazul matricei de adiacenta) :"<<endl;
cout<<"nodul de inceput :";
cin>>k; cout<<k<<endl;
cout<<endl;
for(i=1;i<=n;i++)v[i]=0;
dfm(k);
return 0;
}
