Pagini recente » Cod sursa (job #2653614) | Cod sursa (job #2689035) | Cod sursa (job #2057357) | Cod sursa (job #3199775) | Cod sursa (job #797197)
Cod sursa(job #797197)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 100005
#define maxm 500005
int n,m,grad[maxn],sol[maxm],stiva[maxm] ;
bool sel[maxm] ;
vector < pair<int,int> > v[maxn] ;
bool grad_par()
{
for(int i=1;i<=n;++i)
if( grad[i] & 1 )
return false ;
return true ;
}
bool toate_muchiile ()
{
for(int i=1;i<=m;++i)
if( ! sel[i] )
return false ;
return true ;
}
void euler ()
{
stiva[ ++stiva[0] ] = 1 ;
while( stiva[0] )
{
int nod = stiva[ stiva[0] ] ;
if( v[nod].empty() )
{
sol[ ++sol[0] ] = stiva[ --stiva[0] ] ;
continue ;
}
int varf = v[nod].back().first;
int nrmuchie = v[nod].back().second;
v[nod].pop_back () ;
if( sel[nrmuchie] == false )
{
sel[nrmuchie] = true ;
stiva[ ++stiva[0] ] = varf ;
}
}
}
int main ()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int x,y ;
scanf("%d%d",&x,&y);
v[x].push_back ( make_pair (y, i) ) ;
v[y].push_back ( make_pair (x, i) ) ;
++ grad[x] ;
++ grad[y] ;
}
if( ! grad_par () )
{
printf("-1\n");
return 0 ;
}
euler () ;
if( ! toate_muchiile () )
{
printf("-1\n");
return 0 ;
}
for(int i=1;i<sol[0];++i)
printf("%d\n",sol[i]);
return 0 ;
}