Untitled

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ofstream fout ("scandal.out");
int n,m,x,y,r;
struct rule{
    int x,y,r;
};
vector<rule> R;
vector<int>sol;
int state[100005];
bool solved=false;
bool verif(){
    for (int i=0;i<m;i++){
        rule crt=R[i];
        if (crt.r==0){
            if (state[crt.x]<1&&state[crt.y]<1){
                return false;
            }
        }
        else if (crt.r==1){
            if (state[crt.x]==1&&state[crt.y]==1){
                return false;
            }
        }
        else if (crt.r==2){
            if (state[crt.y]<1&&state[crt.x]==1){
                return false;
            }
        }
    }
    return true;
}
void dfs(int i){
    if (solved){
        return;
    }
    if (i==m){
        if (!verif()){
            return;
        }
        for (int j=1;j<=n;j++){
            if (state[j]==1){
                sol.push_back(j);
            }
        }
        fout<<sol.size()<<"\n";
        for (int j : sol){
            fout<<j<<"\n";
        }
        solved=true;
        return;
    }
    rule crt=R[i];
    if (crt.r==0){
        if (state[crt.x]==1||state[crt.y]==1){
            dfs(i+1);
        }
        else {
            state[crt.x] = 1;
            dfs(i + 1);
            state[crt.x] = -1;
            state[crt.y] = 1;
            dfs(i + 1);
            state[crt.y] = -1;
        }
    }
    else if (crt.r==1){
        if (state[crt.x]==1&&state[crt.y]==1){
            return;
        }
        else{
            if (state[crt.x]==-1){
                state[crt.x]=0;
                dfs(i+1);
                state[crt.x]=-1;
            }
            else if (state[crt.y]==-1){
                state[crt.y]=0;
                dfs(i+1);
                state[crt.y]=-1;
            }
            else{
                dfs(i+1);
            }
        }
    }
    else if (crt.r==2){
        if (state[crt.y]==0&&state[crt.x]==1){
            return;
        }
        else{
            if (state[crt.y]==0){
                state[crt.x]=0;
                dfs(i+1);
                state[crt.x]=0;
            }
            if (state[crt.y]==-1){
                state[crt.y]=state[crt.x];
                dfs(i+1);
                state[crt.y]=-1;
            }
            if (state[crt.y]==1){
                dfs(i+1);
            }
        }
    }
}
int main() {
    ifstream fin ("scandal.in");
    fin>>n>>m;
    for (int i=1;i<=m;i++){
        fin>>x>>y>>r;
        if (r==1){
            swap(x,y);
            r++;
        }
        if (r==3){
            r=1;
        }
        R.push_back({x,y,r});
    }
    sort(R.begin(),R.end(),[](rule a,rule b){
        return a.r<b.r;
    });
    for (int i=1;i<=n;i++){
        state[i]=-1;
    }
    dfs(0);
    return 0;
}