#include <iostream>
using namespace std;
int n, x[10], i, j, k, p, ma[10][10], nrm;
unsigned long int nrs=0;
int bun(int st){
int k;
for(k=1; k<=st-1; k++) if(x[k] == x[st]) return 0;
if((st > 1) && (ma[x[st-1]][x[st]] == 0))return 0;
if(st == n && (ma[x[st]][x[1]]==0)) return 0;
return 1;
}
int main() {
int st;
cin>>n;
cin>>nrm;
for(i=1; i<=n; i++) ma[i][i]=0;
cout<<endl<<"matricea de adiacenta:" << endl << endl;
for(i=1; i<=nrm; i++){
cin>>j>>k;
ma[j][k] = 1;
ma[k][j] = 1;
}
for(i=1; i<=n; i++){
for(j=1; j<=n; j++) cout<<ma[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;
st=1;x[st]=0;
while(st){
p=0;
while(!p && x[st]<n){
x[st]++;
if(bun(st)==1) p=1;
}
if(p==0)st--; //bt
else if(st<n){
st++;
x[st]=0;
}
else{
nrs++;
for(j=1;j<=n;j++)cout<<x[j]<<" ";
cout<<endl;
}
}
cout<<endl<<"am gasit "<<nrs<<" solutii"<<endl;
return 0;
}
