#include <fstream>
#include <iostream>
#include <ctime>
#include <cstdlib>

#define FIN "party.in"
#define FOUT "party.out"

#define MUST 0
#define Y_GOES_WITH_X_ONLY 1
#define X_GOES_WITH_Y_ONLY 2
#define ONE_MUST_NOT_COME 3

struct restriction {
    size_t x, y, op;
};
#define MAX_N 100
#define MAX_M 1000
size_t N, M;
restriction r[MAX_M];

struct SAT_config {
    bool variables[MAX_N];
    size_t score;
};

bool checkRestriction(SAT_config* citizen, restriction* r){
    switch(r->op)
    {
    case(0):
        return citizen->variables[r->x] || citizen->variables[r->y];
    case(1):
        if(!citizen->variables[r->x]) return !citizen->variables[r->y];
        return true;
    case(2):
        if(!citizen->variables[r->y]) return !citizen->variables[r->x];
        return true;
    case(3):
        if(citizen->variables[r->x]) return !citizen->variables[r->y];
        if(citizen->variables[r->y]) return !citizen->variables[r->x];
        return true;
    default:
        return false;
    }
}

void afisareSAT(SAT_config* citizen);

void calculateScore(SAT_config* citizen){
    citizen->score = 0;
    restriction* lastRestriction = r + M;
    std::cout << std::endl;
    afisareSAT(citizen);
    std::cout << std::endl;
    for(restriction* i = r; i < lastRestriction; ++i)
    {
        bool restr = checkRestriction(citizen, i);
        std::cout << i->op << "(" << i->x+1 << "," << i->y+1 << ")->" << (restr ? "true" : "false") << std::endl;
        if(restr) citizen->score++;
    }
}

void afisareSAT(SAT_config* citizen){
    for(size_t i = 0; i < N; ++i)
    {
        if(citizen->variables[i]){
            std::cout << i+1 << " ";
        }
    }
}

size_t numarInvitiati(SAT_config* citizen){
    size_t invitati = 0;
    for(size_t i = 0; i < N; ++i)
    {
        if(citizen->variables[i]){
            ++invitati;
        }
    }
    return invitati;
}

void scriereSAT(SAT_config* citizen, std::ofstream& out){
    size_t invitati = numarInvitiati(citizen);
    out << invitati << std::endl;
    for(size_t i = 0; i < N; ++i)
    {
        if(citizen->variables[i]){
            out << i+1 << std::endl;
        }
    }
}

int main()
{
    std::ifstream in(FIN);
    std::ofstream out(FOUT);

    in >> N >> M;
    for(size_t i = 0; i < M; ++i)
    {
        in >> r[i].x >> r[i].y >> r[i].op;
        --(r[i].x);
        --(r[i].y);
    }

    // abordare genetica
    SAT_config population[MAX_N*MAX_N];
    srand(time(NULL));

    size_t val = 0;
    SAT_config* endPopulation = population+N*N;
    for(SAT_config* i = population; i < endPopulation; ++i)
    {
        bool* endVariables = i->variables+N;
        for(bool* j = i->variables; j < endVariables; ++j)
        {
            val = rand() % 2;
            *j = val ? true : false;
        }
        calculateScore(i);
        std::cout << "Score: " << i->score << std::endl;
        if(i->score == M && numarInvitiati(i) > 0){
            afisareSAT(i);
            scriereSAT(i, out);
            return 0;
        }
    }

    in.close();
    out.close();
    return 0;
}