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

// A graf csucsainak a szama
#define V 3

void printMegoldas(int szin[]);

// Megnezi ha a graph okes vagy sem
bool ezBiztonsagos(int v, bool graph[V][V], int szin[], int c)
{
    for (int i = 0; i < V; i++)
        if (graph[v][i] && c == szin[i])
            return false;

    return true;
}

//Segedfunkcio a szinezes megoldasara
bool graphSzinezes(bool graph[V][V], int m, int szin[],
                       int v)
{

    //Ha minden csucs szint rendel akkor igazat kapunk
    if (v == V)
        return true;

    //tekintsuk a csucsot v-nek es probaljunk ki mas szineket
    for (int c = 1; c <= m; c++) {

        //Megvizsgalja c-tol v ig a szineket hogy rendben van
        if (ezBiztonsagos(v, graph, szin, c)) {
            szin[v] = c;

            //ugyan ugy a tobbi csucsra is
            if (graphSzinezes(graph, m, szin, v + 1)
                == true)
                return true;

            //Ha a c-hez nem kap megoldast akkor tavolitsa el
            szin[v] = 0;
        }
    }

    //Ha nem lehet szint hozza rendelni hamis erteket terit vissza
    return false;
}

//
bool graphSzin(bool graph[V][V], int m)
{

    // Alapbol minden szin erteke 0
    // Szukseges ahhoz hogy az ezbiztonsagos reszlet helyesen mukodjon
    int szin[V];
    for (int i = 0; i < V; i++)
        szin[i] = 0;

    // Meghivja a graph szinezest az elso elre
    if (graphSzinezes(graph, m, szin, 0) == false) {
        cout << "Nincs megoldas";
        return false;
    }

    // Kiirja a megoldast
    printMegoldas(szin);
    return true;
}

//Kiiratas
void printMegoldas(int szin[])
{
    cout << "Talalt megoldast: \n "
         << "A szinezes a kovetkezo:"
         << "\n";
    for (int i = 0; i < V; i++)
        cout << " " << szin[i] << " ";

    cout << "\n";
}


int main()
{

    bool graph[V][V] = {
            { 0, 1, 1,},
            { 1, 0, 1,},
            { 1, 1, 0,},

    };

    // A szinek szama
    int m = 4;
    graphSzin(graph, m);
    return 0;
}