Lant1

#include <fstream>

using namespace std;

ifstream f ("lant1.in");
ofstream g ("lant1.out");

int a[101][101],n,p,q,r,st[101];

void citire()
{
    f>>n>>p>>q>>r;
    int x,y;
    while(f>>x>>y)
    {
        a[x][y]=a[y][x]=1;
    }
}

bool solutie(int k)
{
    int s=0;
    for(int i=1;i<=k && s==0;i++)
        if(st[i]==r)
            s=1;
    if(st[k]==q && s)
        return 1;
    else return 0;
}

void afisare(int k)
{
    for(int i=1;i<=n;i++)
        g<<st[i]<<" ";
}

int dfs(int w)
{
    int k=2;
    st[1]=w;
    while(k>1 && k<=2*n)
    {
        int ok=0;
        for(int i=1;i<=n && ok==0;i++)
            if(a[i][st[k]]==1 && st[k]!=i && st[k-1]!=i)
                ok=1,st[++k]=i;
        if(solutie(k))
            {
            afisare(k);
            return 0;
            }
        else
            if(st[k]==q)
                st[k--]=0; /*banuiesc ca problema este atunci cand
                    coboara un nivel si intra pe exact aceleasi cazuri. Nu pot insa sa folosesc
                    un vector viz[] deoarece se precizeaza ca lantul nu este elementar*/
    }
}

int main()
{
    citire();
    dfs(p);
    return 0;
}