#include <iostream>
#include <vector>
using namespace std;

bool check(vector<vector<int>> mat,vector<int> &color,int c,int v){
    int n=mat.size();
    for(int i=0;i<n;i++){
        if(mat[v][i]==1 && c==color[i]){
            return false;    
        }
    }
    return true;
}
bool solve(vector<vector<int>> mat,int m,vector<int> &color,int v){
    if(v==color.size()){
        return true;
    }
    for(int c=1;c<=m;c++){
        if(check(mat,color,c,v)){
            color[v]=c;
            if(solve(mat,m,color,v+1)){
                return true;
            }
            color[v]=0;
        }
    }
}
int main() {
    int n=4;
    vector<vector<int>> mat={
        {0,1,1,1},
        {1,0,1,0},
        {1,1,0,1},
        {1,0,1,0}
    };
    int m=3;
    vector<int> color(n,0);
    solve(mat,m,color,0);
    return 0;
}