FORCE-T0623A: Graph and String

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

typedef tuple<int, int, int> tiii;

const int N = 500 + 5;

vector<tiii> edges;
vector<int> vt;
int ds[N], sz[N], isWith[N];
char str[N];
bool mat[N][N];

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    int p = dsFind(ds[u]);
    isWith[u] *= isWith[ds[u]];
    return ds[u] = p;
}

int main(){

    int nVertex, nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int u = 1; u <= nVertex; ++u){
        mat[u][u] = true;
        ds[u] = u;
        sz[u] = 1;
        isWith[u] = 1;
    }
    for(int i = 1; i <= nEdge; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        mat[u][v] = true;
        mat[v][u] = true;
    }
    for(int u = 1; u <= nVertex; ++u){
        bool connectedToAll = true;
        for(int v = 1; v <= nVertex; ++v){
            if(!mat[u][v]){
                connectedToAll = false;
                break;
            }
        }
        if(connectedToAll){
            str[u] = 'b';
        } else {
            vt.push_back(u);
        }
    }
    for(int u = 1; u < nVertex; ++u){
        for(int v = u + 1; v <= nVertex; ++v){
            if(binary_search(vt.begin(), vt.end(), u) && binary_search(vt.begin(), vt.end(), v)){
                edges.emplace_back(u, v, mat[u][v] ? 1 : -1);
            }
        }
    }
    for(tiii e : edges){
        int u = get<0>(e);
        int v = get<1>(e);
        int con = get<2>(e);
        int ru = dsFind(u);
        int rv = dsFind(v);
        if(ru != rv){
            if(sz[ru] < sz[rv]){
                swap(ru, rv);
                swap(u, v);
            }
            ds[rv] = ru;
            sz[ru] += sz[rv];
            isWith[rv] = isWith[u] * isWith[v] * con;
        } else if(isWith[u] == isWith[v] && con == -1 || isWith[u] != isWith[v] && con == 1){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes\n";
    for(int u : vt){
        if(isWith[u] == 1){
            str[u] = 'a';
        } else {
            str[u] = 'c';
        }
    }
    printf("%s", str + 1);

    return 0;
}