题意：对每条边定向，使得图中不存在长度为2的路径。
分析：相当于对每个点颜色，类似于二分图染色。然后再check一下合法性即可。
c
o
d
e
:
code:
code:
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <bitset>
#include <vector>
#include<cstring>
#include <stdio.h>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
#define endl "\n"
#define ll long long
#define Mp make_pair
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define Pair pair<int,int>
typedef unsigned long long ull;
#define IO ios::sync_with_stdio(false);
const int N = 1e6+10;
const int maxn = 2e5+5;
vector<int>e[maxn];
//#define int long long
int a[maxn];
map<int,map<int,int>>mp;
int ans[maxn];
bool vis[maxn];
void dfs(int x,int fa,int col)
{
vis[x]=true;
a[x]=col;
for(auto y:e[x]){
if(y==fa||vis[y]) continue;
dfs(y,x,col==-1?1:-1);
}
}
bool flag;
void dfs(int x,int fa)
{
vis[x]=true;
for(auto y:e[x])
{
if(y==fa) continue;
if(a[x]==a[y]) {flag=true; return;}
else if(a[x]==1&&a[y]==-1){
if(mp[x][y]) ans[mp[x][y]]=0;
else ans[mp[y][x]]=1;
}
else if(a[x]==-1&&a[y]==1){
if(mp[y][x]) ans[mp[y][x]]=0;
else ans[mp[x][y]]=1;
}
if(vis[y]) continue;
dfs(y,x);
}
}
void solve()
{
int n,m; cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
mp[u][v]=i;
}
dfs(1,0,1);
memset(vis,false,sizeof vis);
dfs(1,0);
if(flag) {cout<<"NO"<<endl;return;}
cout<<"YES"<<endl;
for(int i=1;i<=m;i++) cout<<ans[i];
}
signed main()
{
// freopen("2.in","r",stdin);
// freopen("15.out","w",stdout);
IO;
//int T; cin>>T;while (T--)
solve();
return 0;
}