CompetitiveProgramming/codeforces/623/A.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)

#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A,n)  { cout << #A << " = "; FOR(_,1,n) cout << A[_] << ' '; cout << endl; }
#define PR0(A,n) { cout << #A << " = "; REP(_,n) cout << A[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
#define SZ(x) ((int) (x).size())
using namespace std;

const int MN = 511;
int n1, n2, m;
bitset<MN> ke1[MN], ke2[MN];
int id[MN], deg[MN];
char color[MN];
vector<int> ls[MN];

void init() {
    FOR(i,1,n1) {
        ke1[i].reset();
        ke2[i].reset();
        id[i] = 0;

        ls[i].clear();
    }
    memset(color, 0, sizeof color);
    memset(deg, 0, sizeof deg);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    while (cin >> n1 >> m) {
        init();
        FOR(i,1,n1) ke1[i][i] = 1;
        FOR(i,1,m) {
            int u, v; cin >> u >> v;
            ke1[u][v] = 1;
            ke1[v][u] = 1;
        }

        n2 = 0;
        FOR(i,1,n1) if (id[i] == 0) {
            ++n2;
            FOR(j,i,n1) if (ke1[i] == ke1[j]) {
                ls[n2].push_back(j);
                id[j] = n2;
            }
        }
//        DEBUG(n2);
//        FOR(i,1,n2) PR0(ls[i], SZ(ls[i]));

        FOR(i,1,n1) FOR(j,i+1,n1) if (ke1[i][j]) {
            int u = id[i], v = id[j];
            if (ke2[u][v] == 1) continue;
            if (u == v) continue;

            ke2[u][v] = ke2[v][u] = 1;
            ++deg[u];
            ++deg[v];
        }

//        PR(deg, n2);

        try {
            FOR(i,1,n2) if (deg[i] > 2) throw 1;

            char cur = 'a';
            FOR(i,1,n2) if (!color[i] && deg[i] <= 1) {
                color[i] = cur;
                int x = i;
                while (true) {
                    bool good = false;
                    FOR(j,1,n2) if (!color[j] && ke2[x][j]) {
                        x = j;
                        color[j] = ++cur;
                        good = true;
                    }
                    if (!good) break;
                }
                cur += 2;
            }
            FOR(i,1,n2) if (!color[i] || color[i] > 'c') throw 1;
            FOR(i,1,n1) {
                if (!color[id[i]]) throw 1;
            }
            cout << "Yes" << endl;
            FOR(i,1,n1) cout << color[id[i]]; cout << endl;
        } catch (int e) {
            cout << "No" << endl;
        }
    }
}