Pagini recente » Cod sursa (job #1854395) | Cod sursa (job #1411956) | Cod sursa (job #745708) | Cod sursa (job #48920) | Cod sursa (job #2290409)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
pair <int,int> v[500001];
int cnt;
int e[500001];
bool marcat[500001],viz[500001];
vector <int> a[100001];
const int dim=1<<17;
char getch()
{
static char buff[dim];
static int bp=dim;
if(bp==dim)
{
bp=0;
fread(buff,1,dim,stdin);
}
return buff[bp++];
}
void get(int &a)
{
a=0;
char ch;
do
{
ch=getch();
}
while(ch<'0'||ch>'9');
do
{
a=a*10+ch-'0';
ch=getch();
}
while('0'<=ch&&ch<='9');
}
void dfs(int x)
{
int muchie,y;
viz[x]=1;
for(int i=0; i<a[x].size(); i++)
{
muchie=a[x][i];
y=v[muchie].second;
if(x==y)
y=v[muchie].first;
if(!viz[y])
dfs(y);
}
}
void euler(int x)
{
int muchie,y;
for(int i=0; i<a[x].size(); i++)
{
muchie=a[x][i];
if(!marcat[muchie])
{
marcat[muchie]=1;
y=v[muchie].second;
if(y==x)
y=v[muchie].first;
euler(y);
}
}
e[++cnt]=x;
}
int main()
{
ios::sync_with_stdio(0);
cout.tie(0);
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
int n,m,i,x,y;
get(n);
get(m);
for(i=1; i<=m; i++)
{
get(x);
get(y);
v[i].first=x;
v[i].second=y;
a[x].push_back(i);
a[y].push_back(i);
}
dfs(1);
for(i=1; i<=n; i++)
if(!viz[i])
{
cout<<"-1";
return 0;
}
for(i=1; i<=n; i++)
if(a[i].size()%2)
cnt++;
if(cnt==0)
{
euler(1);
for(i=1; i<=cnt-1; i++)
cout<<e[i]<<" ";
}
else
cout<<"-1";
return 0;
}