Četiri kanala

U jednom kraljevstvu postoji \(n\) gradova označenih brojevima \(1, 2, \ldots, n\). Neki parovi gradova povezani su drumom.

Kraljevska gradske službe rade na tačno 4 radio-kanala koji su označeni slovima A, B, C, D.

Radio-signal se prenosi duž druma između dva neposredno povezana grada. Ako bi oba grada koristila isti kanal/oznaku, poruke i signali bi se mešali. Zato svaki par gradova povezan drumom mora imati različite kanale/oznake.

Dodeliti svakom gradu jedan od kanala, tako da ne postoje dva grada, povezana drumom, koja imaju isti kanal.

Opis ulaza

Sa standardnog ulaza se prvo unose broj gradova \(n\) (\(1 \leq n \leq 80\)) i broj drumova \(m\) (\(1 \leq m \leq \frac{n(n-1)}{2}\)). U narednih \(m\) redova, unose se drumovi, odnosno dva grada \(u\) i \(v\) koja su povezana drumom (\(1 \leq u < v \leq n\)).

Opis izlaza

Na standardni izlaz:

• Ukoliko dodela postoji, ispisati DA i u zasebnom redu dodeljeni kanal (A, B, C, ili D) za svaki grad \(i\) (\(1 \leq i \leq n\)). Prihvata se samo leksikografski najmanja dodela.
• Ukoliko dodela ne postoji, ipisati NE.

Primer 1

Ulaz

4 4
1 2
2 3
3 4
4 1

Izlaz

DA
A B A B

Objašnjenje

Gradovi su povezani u ciklus, te je dovoljno koristiti samo 2 kanala. Postoji više mogućih dodela, ali leksikogfarski najmanja dodela je A B A B.

Primer 2

Ulaz

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Izlaz

NE

Objašnjenje

Pet gradova gde su bilo koja dva grada povezana drumom. Ukoliko prva četiri grada dobiju kanala A B C D, peti grad ne može dobiti nijedan od kanala A, B, C, ili `D.

Rešenje

#include <iostream>
#include <vector>
#include <string>

using namespace std;

static string channels = "ABCD";

bool assign_channels(vector<char> &assignment, const int u,
                     const vector<vector<int>> &neighbours)
{
    if (u == assignment.size()) {
        return true;
    }

    for (auto channel : channels) {
        bool can_assign = true;

        for (auto v : neighbours[u]) {
            if (assignment[v] == channel) {
                can_assign = false;
            }
        }

        if (can_assign) {
            assignment[u] = channel;
            if (assign_channels(assignment, u + 1, neighbours)) {
                return true;
            }
            assignment[u] = '.';
        }
    }

    return false;
}

void assign(const vector<vector<int>> &neighbours)
{
    int n = neighbours.size();

    vector<char> assignment(n, ' ');
    if (assign_channels(assignment, 0, neighbours)) {
        cout << "DA" << endl;
        for (auto channel : assignment) {
            cout << channel << ' ';
        }
        cout << endl;
    } else {
        cout << "NE" << endl;
    }
}

int main() 
{
    int n, m; cin >> n >> m;

    vector<vector<int>> neighbours(n);

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        neighbours[u - 1].push_back(v - 1);
        neighbours[v - 1].push_back(u - 1);
    }

    assign(neighbours);

    return 0;
}