UVa _ 10004 _ Bicoloring

 def is_bicolorable(adj_list, n):

    for start_node in range(n):

        color = [-1] * n        

        if color[start_node] != -1:

            continue

        # Iterative approach prevents stack overflow for large graphs

        stack = [(start_node, 0)] 

        color[start_node] = 0

        while stack:

            node, node_color = stack.pop()

            next_color = 1 - node_color  # Toggle between 0 and 1

            for neighbor in adj_list[node]:

                if color[neighbor] == -1:

                    color[neighbor] = next_color

                    stack.append((neighbor, next_color))

                elif color[neighbor] == node_color:  # Same color conflict

                    return False

    return True

while True:

    n = int(input())

    if n == 0:

        break

    m = int(input())

    adj_list = [[] for _ in range(n)] # Build adjacency list 

    for _ in range(m):

        a, b = map(int, input().split())

        adj_list[a].append(b)

        adj_list[b].append(a)

    print("BICOLORABLE." if is_bicolorable(adj_list, n) else "NOT BICOLORABLE.")