Cod sursa(job #772393)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream F("ciclueuler.in");
ofstream G("ciclueuler.out");
#define Nmax 100011
typedef vector<int>::iterator Iter;
vector<int> Leg[Nmax];
int Grad[Nmax];
int Marked[Nmax];
int N,M;
vector<int> Rez;
queue<int> Stiva;
void Get( int Nod )
{
Marked[Nod]=1;
for ( Iter it=Leg[Nod].begin() ;it!=Leg[Nod].end() ;++it )
if ( !Marked[ *it ] )
Get( *it );
}
void Erase( int v, int w )
{
--Grad[v];
--Grad[w];
for ( Iter it = Leg[v].begin(),it2 = Leg[v].begin()+1; it2 != Leg[v].end(); ++it,++it2)
swap( *it , *it2 );
Leg[v].pop_back();
for ( Iter it = Leg[w].begin(); it != Leg[w].end(); ++it)
if( *it == v )
{
for (Iter it2 = Leg[w].begin(),it3 = Leg[w].begin()+1; it2 != Leg[w].end()-1; ++it2,++it3)
swap( *it2 , *it3 );
Leg[w].pop_back();
break;
}
}
void Euler( int v )
{
while ( Leg[v].size() )
{
int w = Leg[v].front();
Stiva.push( v );
Erase( v , w );
v = w;
}
}
void Solve()
{
int v=1;
Stiva.push( v );
do
{
Euler( v );
v=Stiva.front();
Stiva.pop();
Rez.push_back( v );
}
while ( Stiva.size() );
}
int main()
{
F>>N>>M;
for (int i=1;i<=M;++i)
{
int x,y;
F>>x>>y;
Leg[x].push_back( y );
if ( x != y ) Leg[y].push_back( x );
++Grad[x];
++Grad[y];
}
Get( 1 );
for (int i=1;i<=N;++i)
if ( Grad[i]%2 || !Grad[i] || !Marked[i] )
{
G<<"-1\n";
return 0;
}
Solve();
for (; Rez.size()>1 ;Rez.pop_back() )
G<<Rez.back()<<' ';
G<<'\n';
}