Codeforces Round #550 (Div. 3) F. Graph Without Long Directed Paths(dfs染色)

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m;
int pre[maxn], a[maxn];
vector<int> v[maxn];

void dfs(int x){
  for(int i=0;i<v[x].size();i++){
    int to = v[x][i];
    if(a[x] == a[to]){
      puts("NO");
      exit(0);
    }
    if(a[x] == -a[to]) continue;
    a[to] = -a[x];
    dfs(to);
  }
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i++){
    int x, y;
    scanf("%d%d",&x,&y);
    v[x].push_back(y);
    v[y].push_back(x);
    pre[i] = x;
  }
  a[1] = 1;
  dfs(1);
  puts("YES");
  for(int i=0;i<m;i++){
    if(a[pre[i]] == 1) cout<<"1";
    else cout<<"0";
  }
  puts("");
  return 0;
}