#include <iostream>
#include <vector>

using namespace std;

// Function to check if assigning a time slot to a class is safe
bool isSafe(int classIndex, vector<vector<int>>& conflicts, vector<int>& timeSlot, int slot) {
    for (int i = 0; i < conflicts.size(); i++) {
        if (conflicts[classIndex][i] && timeSlot[i] == slot) {
            return false;
        }
    }
    return true;
}

// Recursive utility to assign time slots
bool scheduleClassesUtil(vector<vector<int>>& conflicts, int m, vector<int>& timeSlot, int classIndex) {
    if (classIndex == conflicts.size()) {
        return true; // All classes are scheduled
    }

    for (int slot = 1; slot <= m; slot++) {
        if (isSafe(classIndex, conflicts, timeSlot, slot)) {
            timeSlot[classIndex] = slot;
            if (scheduleClassesUtil(conflicts, m, timeSlot, classIndex + 1)) {
                return true;
            }
            timeSlot[classIndex] = 0; // Backtrack
        }
    }
    return false;
}

// Function to find minimum time slots required
int findMinimumTimeSlots(vector<vector<int>>& conflicts) {
    int m = 1;
    while (true) {
        vector<int> timeSlot(conflicts.size(), 0);
        if (scheduleClassesUtil(conflicts, m, timeSlot, 0)) {
            return m;
        }
        m++;
    }
}

// Main function
int main() {
    // Example conflict adjacency matrix
    vector<vector<int>> conflicts = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 1, 0}
    };

    int minTimeSlots = findMinimumTimeSlots(conflicts);
    cout << "Minimum time slots required: " << minTimeSlots << endl;

    return 0;
}