模板

條件

1. 無向圖存在歐拉回路的充要條件是任意一個點的度數都為偶數，且所有的邊是聯通的（也就是除去孤立點外，圖是連通的）
2. 有向圖存在歐拉回路的充要條件是任意一個點的入度等于其出度，且忽略邊的方向后，邊是連通的（同上，等價于除去孤立點外，圖是連通的）
3. 無向圖存在歐拉路徑的充要條件是有且僅有兩個點的度數為奇數，其余為偶數，邊的連通性同上
4. 有向圖存在歐拉路徑的充要條件是有且僅有一個點出度比入度大1（作為起點），一個點入度比出度大1（作為終點），其余點入度等于出度，邊的連通性同上
   （為了方便，這里的歐拉路徑沒有把回路包括在內）
   證明：
   上述條件的必要性是顯然的，考慮證明其充分性，也就是對于任意滿足條件的圖，構造出一組解。
   以無向圖的歐拉路徑為例，首先找到任意一條從起點到終點的路徑（不難發現，這樣的路徑一定存在），然后把這條路徑的邊和孤立點都刪去，那么剩下的子圖一定都與這條路徑有交點，在剩下的子圖中找到一條歐拉回路然后接到這個路徑上就可以了。
   在子圖中找歐拉回路可以遞歸去做，即先找到一個環，然后從環上的每個點出發再找一條歐拉回路……

算法流程

以無向圖歐拉回路為例
與上述的構造類似，我們考慮這樣一個過程：先從任意一個點（作為起點）出發，走一個回路（不一定是簡單環）回到這個點，再從環上的每個點找這個點的歐拉回路，然后把這些歐拉回路插到一開始找到的大環中，這樣可以用鏈表來維護復雜度為線性。
但是實際上用一個dfs+棧就夠了。直接從起點開始dfs，那么第一次回溯一定是在終點（如果是歐拉回路則還是起點），把回溯的這條邊作為歐拉路的最后一條邊，然后回溯到上一個點x，繼續從x進行dfs找歐拉回路并倒序壓入棧中，然后再回溯，再找歐拉回路持續這樣的過程，最終把從棧頂到棧底輸出即為答案。

細節

1. 為了避免重復訪問已經被刪除的邊，要用一個數組存下每個點最后用的過的一條邊，每次在鄰接表上跳下一條邊時不再跳nxt[i]，而是nxt[cur[x]]
2. 判歐拉回路邊的連通性可以用并查集，也可以先當成連通來做，看最后找到的歐拉回路的總邊數是否等于原圖的總邊數。

代碼

#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;
}