Sgu/156

/by Logic
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=10050,maxm=220000;
int n,m,de[2][maxn]={0};
int now,a[2][maxm]={0},pr[2][maxm]={0},ne[2][maxm];
int fa[maxn]={0},fs=0;
int e[maxm][3],es=0,whe[maxm]={0},vis[maxm]={0};
int ans[maxm],anss=0;
void ins(int x,int y,int i)
{
	if(!a[i][x]) a[i][x]=y;
	else 
	{
		now++;
		a[i][now]=y,ne[i][now]=ne[i][x],ne[i][x]=now;
		if(i) pr[i][now]=x;
	}
}
void del(int x)
{
	int i=pr[1][x];
	if(i) ne[1][i]=ne[1][x];
}
int go(int st,int pri)
{
	int i=st,j,s=0,vis0[maxn]={0};
	do
	{
		if(pri) printf("%d ",i);
		vis0[i]=1;
		s++;
		if(a[0][i]==j) j=i,i=a[0][ne[0][i]];
		else j=i,i=a[0][i];
	}while(!vis0[i]);
	return s;
}
int go2(int la,int st,int co,int pri)
{
	int i=st,j=la,qu[maxn],s=0;
	while(de[0][i]==2&&i)
	{
		qu[s++]=i;
		fa[i]=co;
		if(a[0][i]==j) j=i,i=a[0][ne[0][i]];
		else j=i,i=a[0][i];
	}
	if(!pri) return i;
	else if(pri==1)
		for(i=0;i<s;i++)
			printf("%d ",qu[i]);
	else 
		for(i=s-1;i>=0;i--)
			printf("%d ",qu[i]);
	return j;
}
bool judg()
{
	int i;
	for(i=1;i<=n;i++)
		if(de[0][i]!=2) return 1;
	if(go(1,0)<n) {printf("-1\n");return 0;}
	go(1,1);
	return 0;
}
void euler(int pr,int cur,int ed)
{
	int i;
	for(i=cur;a[1][i];i=ne[1][i])
		if(!vis[a[1][i]]) 
		{
			del(i);
			vis[a[1][i]]=1;
			if(fa[e[a[1][i]][2]]==cur&&e[a[1][i]][1]!=pr)
				swap(e[a[1][i]][1],e[a[1][i]][2]),whe[a[1][i]]=1;
			euler(e[a[1][i]][2],fa[e[a[1][i]][2]],a[1][i]);
		}
		else del(i);
	ans[anss++]=ed;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
#endif
	int i,j,x,y,os=0;
	scanf("%d%d",&n,&m);
	now=n;
	for(i=0;i<m;i++)
		scanf("%d%d",&x,&y),ins(x,y,0),ins(y,x,0),de[0][x]++,de[0][y]++;
	if(!judg()) return 0;
	for(i=1;i<=n;i++)
		if(!fa[i]&&de[0][i]>2)
		{
			fa[i]=++fs;
			for(j=i;a[0][j];j=ne[0][j])
				if(de[0][a[0][j]]>2)
					fa[a[0][j]]=fs;
		}
	now=n;
	for(i=1;i<=n;i++)
		if(!fa[i])
		{
			++es;
			int x=go2(i,a[0][i],es,0),y=go2(i,a[0][ne[0][i]],es,0);
			//printf("%d %d %d\n",i,x,y);
			e[es][0]=i,e[es][1]=x,e[es][2]=y;
			ins(fa[x],es,1);
			ins(fa[y],es,1);
			de[1][fa[x]]++;
			de[1][fa[y]]++;
		}
	for(i=1;i<=fs;i++)
		os+=de[1][i]&1;
	if(os) {printf("-1\n");return 0;}
	now=0;
	euler(0,1,0);
	for(i=es-1;i>=0;i--)
	{
		int x=e[ans[i]][0];
		printf("%d ",e[ans[i]][1]);
		go2(x,whe[ans[i]]?a[0][ne[0][x]]:a[0][x],1,2);
		printf("%d ",x);
		go2(x,whe[ans[i]]?a[0][x]:a[0][ne[0][x]],1,1);
		printf("%d ",e[ans[i]][2]);
	}
	return 0;
}