fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x) scanf("%d",&x)
  8. #define sl(x) scanf("%lld",&x)
  9. #define ss(s) scanf("%s",s)
  10. #define pi(x) printf("%d\n",x)
  11. #define pl(x) printf("%lld\n",x)
  12. #define ps(s) printf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<int, int> pii;
  23. typedef pair<ll, ll> pl;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vl;
  26. typedef vector<pii> vpii;
  27. typedef vector<pl> vpl;
  28. typedef vector<vi> vvi;
  29. typedef vector<vl> vvl;
  30. int mpow(int base, int exp);
  31. void ipgraph(int m);
  32. void dfs(int u, int par);
  33. const ll mod = 1000000007*1LL*1000000007;
  34. const int N = 3e5 + 3, M = N;
  35. //=======================
  36.  
  37. set<int> g[N];
  38. int sz[N], par[N];
  39. int rep(int x){
  40. if(x == par[x]) return x;
  41. return par[x] = rep(par[x]);
  42. }
  43. void unite(int x, int y){
  44. x = rep(x);
  45. y = rep(y);
  46. if(x==y)return;
  47. if(sz[x]<sz[y]);
  48. else swap(x, y);
  49. par[x] = y;
  50. if(sz[x] == sz[y])
  51. sz[y]++;
  52. }
  53.  
  54. ll h[N], val[N];
  55. ll r(){
  56. return rand()*32000+rand();
  57. }
  58. map<int,int> taken;
  59. set<ll> allvals;
  60. map<ll, vi> com;
  61. int ass[N], T;
  62. void go(int u){
  63.  
  64. int cur = ass[u];
  65. for(int v: g[u]){
  66. if(ass[v]){
  67. if(abs(ass[v]-ass[u])>1){
  68. cout <<"NO\n";
  69. exit(0);
  70. }
  71. }
  72. else{
  73. if(!taken[cur+1])
  74. ass[v] = cur+1;
  75. else if(!taken[cur-1])
  76. ass[v] = cur-1;
  77. else{
  78. cout <<"NO\n";
  79. exit(0);
  80. }
  81. T = max(T, ass[v]+2);
  82. taken[ass[v]] = 1;
  83. go(v);
  84. }
  85. }
  86. }
  87. int main()
  88. {
  89. ios_base::sync_with_stdio(false);
  90. cin.tie(NULL);
  91. int i,n,k,j, u, v, x, y, a, b, c, m;
  92. cin >> n >> m;
  93. srand(1234);
  94. Fo(i, 1, n+1) h[i] = (r()*r()+r())%mod;
  95. Fo(i, 1, n+1){
  96. par[i] = i;
  97. sz[i] = 0;
  98. }
  99. fo(i, m) {
  100. cin >> u >> v;
  101. g[u].insert(v);
  102. g[v].insert(u);
  103. }
  104. Fo(i, 1, n+1){
  105. val[i] = h[i];
  106. for(int x: g[i]){
  107. val[i] = (val[i] + h[x])%mod;
  108. }
  109. allvals.insert(val[i]);
  110. com[val[i]].pb(i);
  111. }
  112. for(ll c: allvals){
  113. int x = com[c].size();
  114. if(x>1){
  115. u = com[c][0];
  116. for(int v: com[c])
  117. unite(u, v);
  118. }
  119. }
  120. Fo(i, 1, n+1){
  121. set<int> allnew; allnew.clear();
  122. for(int v: g[i]){
  123. allnew.insert(rep(v));
  124. }
  125. g[i].clear();
  126. for(int v: allnew) {
  127. if(v != i)
  128. g[i].insert(v);
  129. }
  130. int nsz = g[i].size();
  131. if(nsz > 2 and i == rep(i)){
  132. cout <<"NO\n";
  133. return 0;
  134. }
  135. }
  136. T = n+2; //take it bigger enough to avoid negative values
  137. Fo(i, 1, n+1){
  138. u = rep(i);
  139. if(u != i) continue;
  140. if(!ass[i]) ass[i] = T,taken[T] = 1, go(i);
  141. }
  142. cout<<"YES\n";
  143. Fo(i, 1, n+1){
  144. cout << ass[rep(i)] << " ";
  145. }
  146. return 0;
  147. }
  148.  
  149.  
Success #stdin #stdout 0s 37504KB
stdin
4 4
1 2
1 3
1 4
3 4
stdout
YES
6 7 5 5