# CFR 794 D. Labelling Cities ( Ad hoc, Graph )

Problem - 794D - Codeforces

N, M ≤ 3e5

O( N lg N )

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

const int MAXN = int( 3e5 );
const int MAXM = int( 3e5 );

int N, M;
vector< int > G[ MAXN ];
vector< int > tmp[ MAXN ];
int id[ MAXN ];

int gans[ MAXN ];
void dfs( int u, int fa, int cnt ) {
gans[ u ] = cnt;
for( int v: gadj[ u ] ) {
if( v == fa ) continue;
dfs( v, u, cnt + 1 );
}
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < M; ++i ) {
int u, v;
cin >> u >> v;
G[ u - 1 ].emplace_back( v - 1 );
G[ v - 1 ].emplace_back( u - 1 );
}
for( int i = 0; i < N; ++i ) {
G[ i ].emplace_back( i );
sort( G[ i ].begin(), G[ i ].end() );
tmp[ i ] = G[ i ];
}
sort( tmp, tmp + N );
int usize = unique( tmp, tmp + N ) - tmp;
if( usize == 1 ) {
cout << "YES" << endl;
for( int i = 0; i < N; ++i ) {
cout << 1 << " \n"[ i + 1 == N ];
}
exit( 0 );
}
for( int i = 0; i < N; ++i ) {
id[ i ] = lower_bound( tmp, tmp + usize, G[ i ] ) - tmp;
}
for( int i = 0; i < N; ++i ) {
for( int j = 0; j < G[ i ].size(); ++j ) {
if( id[ i ] == id[ G[ i ][ j ] ] ) continue;
gadj[ id[ i ] ].emplace( id[ G[ i ][ j ] ] );
gadj[ id[ G[ i ][ j ] ] ].emplace( id[ i ] );
}
}
int deg1 = 0, st;
for( int i = 0; i < usize; ++i ) {
if( gadj[ i ].size() > 2 ) {
cout << "NO" << endl;
exit( 0 );
}
if( gadj[ i ].size() == 1 ) {
++deg1;
st = i;
}
}
if( not ( 1 <= deg1 and deg1 <= 2 ) ) {
cout << "NO" << endl;
exit( 0 );
}
dfs( st, -1, 1 );
cout << "YES" << endl;
for( int i = 0; i < N; ++i ) {
cout << gans[ id[ i ] ] << " \n"[ i + 1 == N ];
}
return 0;
}
```