#include<iostream>
#include<stdio.h>
#define NMaxOrase 20
 using namespace std;
 int T[NMaxOrase], a[NMaxOrase][NMaxOrase], k, n, i,NrSol;

void citire( )
{int m, start, stop;
 for (i=1;i<=n;i++)			//initializam matricea
for(int j=1;j<=n;j++) a[i][j]=0;
printf("numar de trasee, m="); 	//citesc numarul de muchii din graf
scanf("%d",&m);

cout<<"\ntraseul are start si stop\n";
for(int j=1;j<=m;j++)			 //marchez in matrice arcele grafului
{printf("\nstart ="); scanf("%d",&start);
  printf(" stop ="); scanf("%d",&stop);
  a[start][ stop]=1; a[stop][ start]=1; }}

//int succesor ( )
//{if (T[k]<n){T[k]++; return 1; }return 0; }



bool valid(int k)
{ //bool ok=1;
if(a[T[k]][T[k-1]]==0)//testez daca 2orase selectate sunt vecine, au traseu
 return 0;
 if((k==n)&&(a[T[k]][T[1]]==0)) //testez daca primul oras este ≠ de ult.
return 0;
for(i=1;i<k;i++)if(T[k]==T[i])//testez sa nu vizit. orasul de mai multe ori
return 0;return 1;}

int solutie ( )
{if (k-1==n)return 1;return 0;}// traseul e complet-am vizitat toate orasele

void afisare()
{for (i=1;i<=n+1;i++) // parcurg vectorul solutie si il afisez
cout<< T[i]<<" "; printf ("\n");}



void bkt()
{T[i]=1; k=2;
 T[1]=1;        //curierul pleaca din orasul1
 while (k>1)
 if (solutie()) { afisare(); k--; }
else if (T[k]<n)
//if (T[k]<n)inseamna ca mai sunt noduri neviz., continua valid
{ T[k]++;if(valid(k)) k++; }
else { T[k]=0; k--; } }

//void bkt()
//{bool ok; //k=1; s[k]=0;
//T[i]=1; k=2;
// T[1]=1;
//while(k>1)
//    {ok = 0;while(T[k]<n && !ok){T[k]++;if (valid(k))ok = 1;}
//if (ok)if (solutie()){NrSol++;afisare();}
//            else{k++;T[k]=0;}
//    else k--;}
//cout<<"Total: "<<NrSol<<" solutii."<<endl;}




 int main()
{printf("numar de orase, n="); //citesc numarul de puncte din graf
scanf("%d",&n);
citire ( );
T[n+1]=1;			 //initializez ultimul element cu 1
 cout<<"\nafisare trasee\n\n"; bkt();}