from random import randint

def ramsey(G):
    if not G:
        return set(), set()
    idx = randint(0, len(G) - 1)
    nodes = list(G.keys())
    node = nodes[idx]
    neighbors = (nbr for nbr in G[node] if nbr != node)
    
    non_neighbors = [n for n in nodes if not n in G[node]]
    G1 = {node : iset for node, iset in G.items() if node in neighbors}
    G2 = {node : iset for node, iset in G.items() if node in non_neighbors}
    c_1, i_1 = ramsey(G1)
    c_2, i_2 = ramsey(G2)

    c_1.add(node)
    i_2.add(node)
    return max(c_1, c_2, key=len), max(i_1, i_2, key=len)

def complement(G):
    _G = {node: set() for node in G}
    for n in _G:
        for m in G:
            if not m in G[n]:
                _G[n].add(m)
    return _G
    
def max_clique(G):
    cgraph = complement(G)
    iset, _ = clique_removal(cgraph)
    return iset



def clique_removal(G):
    graph = G.copy()
    c_i, i_i = ramsey(graph)
    cliques = [c_i]
    isets = [i_i]
    while graph:
        for c in c_i:
            del graph[c]
        c_i, i_i = ramsey(graph)
        if c_i:
            cliques.append(c_i)
        if i_i:
            isets.append(i_i)
    # Determine the largest independent set
    maxiset = max(isets, key=len)
    return maxiset, cliques
    
def maximum_clique(arr):
    n, m = len(arr), len(arr[0])
    G = {i: set() for i in range(n)}
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                G[i].add(j)
    print(G)
    mc = max_clique(G)
    return mc
    
arr = [[0, 0, 1, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 0, 0, 1], [1, 0, 0, 0, 0, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 1, 0, 1, 1, 1], [1, 1, 0, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 0, 1, 1, 1, 1], [0, 1, 1, 0, 1, 1, 0, 0, 1, 1], [0, 0, 1, 1, 1, 1, 0, 0, 1, 0], [0, 0, 1, 1, 1, 1, 1, 1, 0, 1], [0, 1, 0, 1, 1, 1, 1, 0, 1, 0]]

cc = maximum_clique(arr)
print(cc)