条件
- 无向图存在欧拉回路的充要条件是任意一个点的度数都为偶数，且所有的边是联通的（也就是除去孤立点外，图是连通的）
- 有向图存在欧拉回路的充要条件是任意一个点的入度等于其出度，且忽略边的方向后，边是连通的（同上，等价于除去孤立点外，图是连通的）
- 无向图存在欧拉路径的充要条件是有且仅有两个点的度数为奇数，其余为偶数，边的连通性同上
- 有向图存在欧拉路径的充要条件是有且仅有一个点出度比入度大1（作为起点），一个点入度比出度大1（作为终点），其余点入度等于出度，边的连通性同上
（为了方便，这里的欧拉路径没有把回路包括在内）
证明：
上述条件的必要性是显然的，考虑证明其充分性，也就是对于任意满足条件的图，构造出一组解。
以无向图的欧拉路径为例，首先找到任意一条从起点到终点的路径（不难发现，这样的路径一定存在），然后把这条路径的边和孤立点都删去，那么剩下的子图一定都与这条路径有交点，在剩下的子图中找到一条欧拉回路然后接到这个路径上就可以了。
在子图中找欧拉回路可以递归去做，即先找到一个环，然后从环上的每个点出发再找一条欧拉回路……
算法流程
以无向图欧拉回路为例
与上述的构造类似，我们考虑这样一个过程：先从任意一个点（作为起点）出发，走一个回路（不一定是简单环）回到这个点，再从环上的每个点找这个点的欧拉回路，然后把这些欧拉回路插到一开始找到的大环中，这样可以用链表来维护复杂度为线性。
但是实际上用一个dfs+栈就够了。直接从起点开始dfs，那么第一次回溯一定是在终点（如果是欧拉回路则还是起点），把回溯的这条边作为欧拉路的最后一条边，然后回溯到上一个点x，继续从x进行dfs找欧拉回路并倒序压入栈中，然后再回溯，再找欧拉回路持续这样的过程，最终把从栈顶到栈底输出即为答案。
细节
- 为了避免重复访问已经被删除的边，要用一个数组存下每个点最后用的过的一条边，每次在邻接表上跳下一条边时不再跳nxt[i]，而是nxt[cur[x]]
- 判欧拉回路边的连通性可以用并查集，也可以先当成连通来做，看最后找到的欧拉回路的总边数是否等于原图的总边数。
代码
#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define db long double
int rd()
{
int x=0,w=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),w=-1;
while(isdigit(ch)) x=x*10+(ch-48),ch=getchar();
return x*w;
}
const int N=2e5+100;
int n,m,ind[N],od[N],deg[N],hd[N],cnt=1,fa[N<<1];
struct node{
int nxt,to,id;
}e[N<<1];
int vis[N<<1];
int op,stk[N<<1],top;
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void dfs(int x)
{
// cout<<hd[x]<<endl;
// if(hd[x]==3){
// puts("jjjjlllll");
// }
for(int i=hd[x];i;i=e[hd[x]].nxt)
{
hd[x]=i;
if(vis[i]) continue;
vis[i]=1;if(op&1) vis[i^1]=1;
dfs(e[i].to);
stk[++top]=e[i].id;
}
}
void add(int x,int y,int id)
{
++cnt;
e[cnt]={hd[x],y,id};
hd[x]=cnt;
}
signed main()
{
// freopen("data.in","r",stdin);
op=rd();n=rd();m=rd();for(int i=1;i<=n+m;++i) fa[i]=i;
if(op&1)
{
for(int i=1;i<=m;++i){
int x=rd(),y=rd();
int fx=find(x),fy=find(y);
fa[fx]=fy;fa[n+i]=fy;
add(x,y,i);deg[x]++;
add(y,x,-i);deg[y]++;
}
// for(int i=1;i<=n;++i) cout<<deg[i]<<endl;
for(int i=1;i<=n;++i) if(deg[i]&1) {
puts("NO");return 0;
}
for(int i=2;i<=m;++i) if(find(n+i)!=find(n+i-1)){
puts("NO");return 0;
}
puts("YES");
for(int i=1;i<=n;++i) dfs(i);
while(top) cout<<stk[top--]<<' ';
return 0;
}
for(int i=1;i<=m;++i){
int x=rd(),y=rd();
add(x,y,i);ind[y]++;od[x]++;
int fx=find(x),fy=find(y);
fa[fx]=fy;fa[n+i]=fy;
}
for(int i=1;i<=n;++i) if(ind[i]!=od[i]){
puts("NO");return 0;
}
for(int i=2;i<=m;++i) if(find(i+n)!=find(i+n-1)){
puts("NO");return 0;
}
puts("YES");
for(int i=1;i<=n;++i) dfs(i);
while(top) cout<<stk[top--]<<' ';
return 0;
}