Pagini recente » Cod sursa (job #703449) | Cod sursa (job #383280) | Cod sursa (job #1252839) | Cod sursa (job #2056204) | Cod sursa (job #3162152)
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
int i,n,m,nr;
vector<int>rsp;
struct nodus
{
int nxt,nrmuc;
};
bool vazut[500001];
vector<nodus> graf_muchii[100001];
void eulerian(int nodincep)
{
stack<int> stk;
stk.push(nodincep);
while(!stk.empty())
{
int nod=stk.top();
if(!graf_muchii[nod].empty())
{
nodus muchie = graf_muchii[nod].back();
graf_muchii[nod].pop_back();
if(!vazut[muchie.nrmuc])
{
vazut[muchie.nrmuc]=1;
stk.push(muchie.nxt);
}
}
else
{
stk.pop();
rsp.push_back(nod);
}
}
}
bool prea_mult_impar()
{
for(i=1; i<=n; i++)
{
if(graf_muchii[i].size()%2==1)
{
return 0;
}
}
return 1;
}
/*bool conex()
{
bool viz[100001]= {0};
int nodviz=1;
queue<int> que;
que.push(1);
viz[1]=1;
while(!que.empty())
{
int nod=que.front();
que.pop();
for(auto vecin:graf_muchii[nod])
{
if(!viz[vecin.nod])
{
nodviz++;
viz[vecin.nod]=1;
que.push(vecin.nod);
}
}
}
return nodviz==n;
}
*/
int main()
{
cin>>n>>m;
for(i=1; i<=m; i++)
{
int x,y;
cin>>x>>y;
graf_muchii[x].push_back({y,i});
graf_muchii[y].push_back({x,i});
}
/*if(!conex())
{
cout<<-1;
return 0;
}
*/
if(!prea_mult_impar())
{
cout<<-1;
return 0;
}
eulerian(1);
for(i=0; i<(int)rsp.size()-1; i++)
cout<<rsp[i]<<" ";
return 0;
}