Pagini recente » Cod sursa (job #2318641) | Cod sursa (job #3001528) | Cod sursa (job #3187060) | Cod sursa (job #780705) | Cod sursa (job #1316525)
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <math.h>
#include <algorithm>
#include <bitset>
#define pb push_back
#define x first
#define y second
using namespace std ;
const int NMAX = 500005 ;
const int INF = 0x3f3f3f3f ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> Pair ;
ifstream fin("ciclueuler.in") ;
ofstream fout("ciclueuler.out") ;
int N, M ;
void READ() ;
void SOLVE() ;
void OUT() ;
void EULER(int) ;
bool CEUlER() ;
void DFS(int) ;
bool visited[NMAX] ;
vector <int> sol ;
stack <int> S ;
vector <int> V[NMAX] ;
int PAR[NMAX] ;
inline void READ()
{
fin >> N >> M ;
for(int i = 1 ; i <= M ; ++ i)
{
int X, Y ;
fin >> X >> Y ;
V[X].pb(Y) ;
V[Y].pb(X) ;
PAR[X] ++ ;
PAR[Y] ++ ;
}
}
void DFS(int node)
{
visited[node] = true ;
for( unsigned i = 0 ; i < V[node].size() ; ++ i)
{
int neighbor = V[node][i] ;
if(!visited[neighbor])
DFS(neighbor) ;
}
}
bool CEUlER()
{
for(int i = 1 ; i <= N ; ++ i)
if( !visited[ i ] || PAR[i] % 2 != 0 )
return false ;
return true ;
}
inline void EULER(int v)
{
while(1)
{
if( V[v].empty() )
break ;
int w = V[ v ][ V[v].size() - 1 ] ;
for(unsigned i = 0 ; i < V[w].size() ; i ++)
if(V[w][i] == v)
{
V[w].erase( V[w].begin() + i) ;
break ;
}
v = w ;}
}
inline void SOLVE()
{
DFS(1) ;
if(CEUlER())
{
int v = 1 ;
do {
EULER(v) ;
v = S.top() ;
S.pop() ;
sol.pb(v) ;
}while( !S.empty() ) ;
for(unsigned i = 0 ; i < sol.size() ; ++ i)
fout << sol[i] << ' ' ;
}
else fout << "-1\n" ;
}
int main()
{
READ() ;
SOLVE() ;
fin.close() ;
fout.close() ;
return 0 ;
}