1 #include<cstdio> 2 const int maxn=1e5+10; 3 const int maxm=5e5+10; 4 int t,n,m,s; 5 int a,b; 6 int ld[maxn],cd[maxn],lj[maxn]; 7 int h[maxn],hs=1; 8 int e_s[maxm],e_n[maxm]; 9 bool v[maxm],ans;10 void dfs(int k,int step){11     if(step>m){ans=1;return;}12     for(int i=h[k];i;i=e_n[i])13     if(!v[i]){14         lj[step]=i;15         v[i]=1;16         if(t==1) v[i^1]=1;17         dfs(e_s[i],step+1);18         v[i]=0;19         if(t==1) v[i^1]=0;20         if(ans) return;21     }22 }23 int main(){24     scanf("%d%d%d",&t,&n,&m);25     if(n==1){puts("YES");return 0;}26     for(int i=1;i<=m;i++){27         scanf("%d%d",&a,&b);28         ++hs,e_s[hs]=b,e_n[hs]=h[a],h[a]=hs,++cd[a],++ld[b];29         if(t==1) ++hs,e_s[hs]=a,e_n[hs]=h[b],h[b]=hs,++cd[b],++ld[a];30     }31     for(int i=1;i<=n;i++){32         if((ld[i]&1&&t==1)||(ld[i]!=cd[i]&&t==2)){puts("NO");return 0;}33         if(cd[i]) s=i;34     }35     puts("YES");36     dfs(s,1);37     for(int i=1;i<=m;i++){38         if(t==1){39             if(lj[i]&1) putchar(‘-‘);40             printf("%d",lj[i]>>1);41         }42         if(t==2) printf("%d",lj[i]-1);43         if(i!=m) putchar(‘ ‘);44     }45     putchar(‘\n‘);46     return 0;47 }