题目：http://codeforces.com/contest/36/problem/E
找出两条欧拉路覆盖无向图。
套上欧拉路模板。用过的边要记录。
注意 一个连通块、4个奇度数点 的情况是在两个奇度数点之间连一条边，跑完欧拉路后再断开！而不是……
特别奇怪的一点是如果不写那个 跑完欧拉路后发现队列里的边不足m条就输出-1 就会WA。
但Zinn没有这个特判，我也觉得这种情况很奇怪。可能是代码别的地方写错了？
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e4+;
int n,m,mp[N],hd[N],xnt,deg[N],col[N],cnt;
int sta[N],top,q[N],jd,ct1;
bool use[N],vis[N];
struct Ed{
int nxt,to,bh;Ed(int n=,int t=,int b=):nxt(n),to(t),bh(b) {}
}ed[N<<];
void add(int x,int y,int b)
{
ed[++xnt]=Ed(hd[x],y,b);hd[x]=xnt;
ed[++xnt]=Ed(hd[y],x,b);hd[y]=xnt;
}
void dfs(int cr)
{
col[cr]=cnt;if(deg[cr]&)q[++jd]=cr;
for(int i=hd[cr];i;i=ed[i].nxt)
if(!col[ed[i].to])dfs(ed[i].to);
}
void dfs(int rt,int cr,int fa)
{
vis[cr]=;
for(int i=hd[cr];i;/*i=hd[cr]*/i=ed[i].nxt)
if(!use[ed[i].bh])
{
// hd[cr]=ed[i].nxt;//!
use[ed[i].bh]=;
dfs(rt,ed[i].to,cr);
sta[++top]=ed[i].bh;
if(ed[i].bh==m+)ct1=--top;
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&m);int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(!mp[x])mp[x]=++n;
if(!mp[y])mp[y]=++n;
deg[mp[x]]++;deg[mp[y]]++;
add(mp[x],mp[y],i);
}
for(int i=;i<=n;i++)
if(!col[i])
{
cnt++;dfs(i);
}
if(cnt>||jd>||m==){printf("-1\n");return ;}
if(cnt==&&jd==&&col[q[]]==col[q[]]==col[q[]]==col[q[]]){printf("-1\n");return ;}
memset(vis,,sizeof vis);
if(cnt==)
{
if(jd)
{
dfs(q[],q[],);ct1=top;
if(jd==)
{
for(int i=;i<=n;i++)
if(!vis[i]){dfs(i,i,);break;}
}
else{
for(int i=;i<=;i++)
if(!vis[q[i]]){dfs(q[i],q[i],);break;}
}
}
else{
dfs(,,);ct1=top;
for(int i=;i<=n;i++)if(!vis[i]){dfs(i,i,);break;}
}
}
else{
if(jd)
{
if(jd==){
add(q[],q[],m+);dfs(q[],q[],);/////////
}
else dfs(q[],q[],),ct1=top;
}
else ct1=m,dfs(,,);
}
if(top!=m){printf("-1");return ;}///////?
if(ct1==top)
{
printf("1\n%d\n",sta[top]);
printf("%d\n",ct1-);
for(int i=top-;i;i--)printf("%d ",sta[i]);
return ;
}
printf("%d\n",ct1);
for(int i=ct1;i;i--)
printf("%d ",sta[i]);
printf("\n");
printf("%d\n",top-ct1);
for(int i=top;i>ct1;i--)
printf("%d ",sta[i]);
return ;
}