infoarena

S = multime vida de cicluri
reprezentare prin liste de adiacenta (cu cate doua muchii orientate pt. fiecare din enunt)
cat timp graf mai are muchii
  fa dfs si gaseste un ciclu C
  pentru fiecare ciclu X din multimea de cicluri S
    daca C il atinge pe X
       uneste C cu X; elimina pe X din S
   adauga pe C la X
scrie unicul (?) ciclu ramas in S

DFS(nod)
{
   pentru fiecare vecin X al lui nod
   {
       sterge muchia (nod, X)
       DFS(X)
   }
   ciclu(count) = nod;
   count = count + 1;
}

void dfs(int x)
{
    while (!g[x].empty())
    {
        int y = g[x].front();
        g[x].pop_front();
        dfs(y);
    }
    cycle.push_back(x+1);
}

vector<list<int> > g;

#include <iostream> // for debug
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
#include <iterator>

#define ALL(c) (c).begin(), (c).end()

using namespace std;

vector<list<int> > g;
vector<int> cycle;

void dfs(int x)
{
    while (!g[x].empty())
    {
        int y = g[x].front();
        g[x].pop_front();
        dfs(y);
    }
    cycle.push_back(x+1);
}


int main()
{
    ifstream inf("watchcow.in");
    ofstream outf("watchcow.out");
    istream& in = inf; // for debug: just change inf to cin to work with console
    ostream& out = outf; // for debug: just change outf to cout to work with console

    int N, M;
    in >> N >> M;
    g.resize(N);
    int i, j;
    int a, b;
    for (i = 0; i < M; ++i)
    {
        in >> a >> b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }

    dfs(0);
    copy(ALL(cycle), ostream_iterator<int>(out, "\n"));
}