<题目链接>
题目大意：
给定一个无向图，该无向图不含自环，且无重边。现在要你将这个无向图定向，使得不存在任何一条路径长度大于等于2。然后根输入边的顺序，输出构造的有向图。如果构造的边与输入的方向一致，就输出1，方向不一致就输出0。
解题分析：
因为定向后的图不能存在长度大于等于2的路径，所以我们直接对原图进行奇偶染色。如果碰到了奇环，就直接输出"NO"，否则就对该图奇偶染色，进行地定向。$col[u]$表示以$u$为起点的边所染的颜色。
#include <bits/stdc++.h>
using namespace std; #define pb push_back
const int N = 2e5+; template<typename T>
inline void read(T&x){
x=;int f=;char c=getchar();
while(c<'' || c>''){ if(c=='-')f=-;c=getchar(); }
while(c>='' && c<=''){ x=x*+c-'';c=getchar(); }
x*=f;
}
int n,m;
int vis[N],col[N];
vector<int>G[N],index;
bool ok=true; void dfs(int u,int cur){
col[u]=cur;
vis[u]=;
for(auto v:G[u]){
if(col[v] && col[u]==col[v]) ok=false; //出现冲突
if(!vis[v]){
if(cur&)dfs(v,);
else dfs(v,);
}
}
}
int main(){
read(n);read(m);
for(int i=;i<=m;i++){
int u,v;read(u);read(v);
G[u].pb(v);G[v].pb(u);
index.pb(u); //记录下第i条边的起点
}
dfs(,);
if(!ok)return puts("NO"),;
puts("YES");
for(auto u:index){
printf("%d",col[u]-);
}puts("");
}