欧拉回路

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=400010;
int h[N],e[M],ne[M],idx;
int din[N];
int dout[N];
bool st[M];
int cnt;
int type;
int ans[M];
int p[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    //cout<<u<<endl;
    for(int &i=h[u];~i;)
    {
        int tmp=i;
        if(st[i])
        {
            i=ne[i];
            continue;
        }
       st[i]=1;
       if(type==1)
       st[i^1]=1;
       int j=e[i];
       dfs(j);
       if(type==2)
       ans[++cnt]=tmp+1;
       else
       {
           //cout<<tmp<<endl;
           int t=(tmp)/2+1;
           if(tmp&1) t=-t;
           ans[++cnt]=t;
       }

    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>type;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        if(type==1)
        {
            add(b,a);
        }
        din[b]++;
        dout[a]++;
    }
    if(type==1)
    for(int i=1;i<=n;i++)
    {
        if(din[i]+dout[i]&1)
        {
          //  cout<<din[i]<<" "<<dout[i]<<" "<<i<<endl;
            cout<<"NO"<<endl;
            return 0;
        }
    }
    else
    {
        for(int i=1;i<=n;i++)
        if(din[i]!=dout[i])
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }

    for(int i=1;i<=n;i++)
    if(h[i]!=-1)
    {
        dfs(i);
        break;
    }


     if(cnt!=m)
    {
        cout<<"NO"<<endl;
        return 0;
    }



    cout<<"YES"<<endl;
    for(int i=cnt;i>=1;i--)
    cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}