Submission #39266281

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const long long MAX = 1e5 * 2 + 5;
vector<long long> p(MAX), d(MAX, 0);

pair<long long,long long> root(long long x){
   if(p[x] == x) return {x, 0};
   auto pa = root(p[x]);
   d[x] = d[x] + pa.second;
   p[x] = pa.first;
   return {p[x], d[x]};
}
  

void unite(long long x, long long y){
    auto z = root(x);
    p[y] = z.first;
    d[y] = z.second + 1;
    return;
}
    
int main(){

 long long n, m;
 cin >> n >> m;
  
 for(int i=1; i<=n; i++) p[i] = i;

 for(int i=1; i<=m; i++){
    int x, y;
    cin >> x >> y;
    unite(x,y);
 }

 set<long long> st;
 long long rt = root(1).first;
 vector<long long> ans(n+1);
 for(int i=1; i<=n; i++){
    auto x = root(i);    
    if(x.first != rt || st.find(x.second) != st.end()){
          cout << "No" << endl;
          return 0;
    }
    st.insert(x.second);
    ans[i] = x.second + 1;
 }

 cout << "Yes" << endl;
 for(int i=1; i<=n; i++) cout << ans[i] << " ";
 cout << endl;
 return 0;
}

Submission Info

Judge Result