Pagini recente » Cod sursa (job #334763) | Cod sursa (job #2772391) | Cod sursa (job #681464) | Cod sursa (job #777508) | Cod sursa (job #1280912)
#include <fstream>
#include <vector>
#include <stack>
#define NMax 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int N,M;
vector <int> G[NMax],Sol;
stack <int> S;
int Grad[NMax],Ok=1,Use[NMax];
void Read()
{
fin>>N>>M;
for(int i=1;i<=M;i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
Grad[x]++;
Grad[y]++;
}
}
void DFS(int Nod)
{
Use[Nod] = 1;
for(unsigned int i= 0; i<G[Nod].size();i++)
{
int Vecin = G[Nod][i];
if(!Use[Vecin])
DFS(Vecin);
}
}
void Erase(int Nod1, int Nod2)
{
G[Nod1].erase(G[Nod1].begin());
for(unsigned int i = 0; i<G[Nod2].size(); i++)
if(G[Nod2][i]==Nod1)
{
G[Nod2].erase(G[Nod2].begin()+i);
break;
}
}
void Cycle(int Nod)
{
while(G[Nod].size())
{
S.push(Nod);
int Vecin = G[Nod][0];
Erase(Nod,Vecin);
Nod = Vecin;
}
}
void Solve()
{
DFS(1);
for(int i = 1; i<=N; i++)
if(Grad[i]%2==1)
Ok=0;
for(int i = 1; i<=N; i++)
if(!Use[i])
Ok=0;
if(!Ok) return;
int Nod=1;
do
{
Cycle(Nod);
Nod = S.top(); S.pop();
Sol.push_back(Nod);
}
while(!S.empty());
}
void Print()
{
if(!Ok)
{
fout<<"-1\n";
return;
}
for(unsigned int i = 0 ; i<Sol.size(); i++)
fout<<Sol[i]<<" ";
fout<<"\n";
}
int main()
{
Read();
Solve();
Print();
return 0;
}