AIM Tech Round 2C

ATR_2C.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;

template <typename T>
inline void output(T a, int p) {
    if(p){
        cout << fixed << setprecision(p)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N, M;
    cin >> N >> M;
    vector<vector<int>> R(N, vector<int>(N, 0));
    vector<vector<int>> E(N);
    rep(i, M){
        int f, t;
        cin >> f >> t;
        f--, t--;
        R[f][t] = R[t][f] = 1;
        E[f].pb(t), E[t].pb(f);
    }

    string s = "";
    rep(i, N) s += "b";
    vector<vector<int>> L(N);
    vector<int> vis(N, 1);
    int c = -1;
    rep(i, N) repd(j, i + 1, N) if(R[i][j] == 0) L[i].pb(j), L[j].pb(i), c = i, vis[i] = vis[j] = 0;
    if (c == -1) {
        output("Yes", 0);
        output(s, 0);
        return 0;
    }
    
    queue<int> q; // bfs
    q.push(c);
    s[c] = 'a';
    vis[c] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        rep(i, L[t].size()){
            if (s[L[t][i]] == 'b') {
                q.push(L[t][i]);
                s[L[t][i]] = (s[t] == 'a') ? 'c' : 'a';
                vis[L[t][i]] = 1;
            }
        }
    }
    
    rep(i, N){
        if (vis[i] == 0) { // if subgraph is connected
            output("No", 0);
            return 0;
        }
        rep(j, L[i].size()){ // are there distinct x-x pairs
            if (s[i] == s[L[i][j]]) {
                output("No", 0);
                return 0;
            }
        }
        rep(j, E[i].size()){
            if (abs(s[i] - s[E[i][j]]) == 2) { // are there a-c edges
                output("No", 0);
                return 0;
            }
        }
    }
    
    
    output("Yes", 0);
    output(s, 0);
    
    return 0;
}