#!/usr/bin/env python3

import random


class Node(object):

    def __init__(self, index):
        self.index = index
        self.neighbors = set()
        self.color = None

    def __str__(self):
        ns = len(self.neighbors)
        return "N({}, {}, color={})".format(self.index, ns, self.color)

    def __repr__(self):
        return self.__str__()

    def is_feasible(self, color):
        """ Returns True if color can be assigned without causing
        a violation with a neighbor. """
        assert(color is not None)
        for nb in self.neighbors:
            if nb.color == color:
                return False
        return True

    def get_color_count(self, color):
        """ Returns how many neighbors with that color exist. """
        return sum([1 for n in self.neighbors if n.color == color])

    def neighbors_by_color(self, max_color):
        neighbors = {c: [] for c in range(0, max_color)}
        for nb in self.neighbors:
            neighbors[nb.color].append(nb)
        return neighbors

    def get_neighbors_by_color(self, color):
        return [nb for nb in self.neighbors if nb.color == color]


def parse(input_data):
    # parse the input
    lines = input_data.split('\n')
    node_count, edge_count = map(int, lines[0].split())
    nodes = [Node(i) for i in range(node_count)]

    for i in range(1, edge_count + 1):
        n_1, n_2 = map(int, lines[i].split())
        nodes[n_1].neighbors.add(nodes[n_2])
        nodes[n_2].neighbors.add(nodes[n_1])
    return nodes


def greedy_old(nodes, color):

    def branch(nodes):
        if not nodes:
            return nodes

        min_node = min(nodes, key=lambda n: len(n.colors))
        nodes.remove(min_node)

        min_node.color = min_node.colors.pop()
        for nb in min_node.neighbors:
            nb.colors.discard(min_node.color)
        return nodes

    def prune(nodes, color):
        node = None
        for n in nodes:
            if not n.colors:
                node = n
                break

        while node:
            assert(node.color is None)
            node.color = color
            next_node = None
            next_nodes = []
            for n in nodes:
                if n is node:
                    continue

                if n not in node.neighbors:
                    n.colors.add(color)

                if next_node is None and not n.colors:
                    next_node = n

                next_nodes.append(n)
            color += 1
            nodes = next_nodes
            node = next_node
        return nodes, color

    while nodes:
        nodes, color = prune(nodes, color)
        nodes = branch(nodes)
    return nodes


def kemp_chain(node, color_a, color_b):
    assert(node.color == color_a)
    visited = set()
    to_invert = set([node])
    while to_invert:
        n = to_invert.pop()
        visited.add(n)

        if n.color == color_a:
            n.color = color_b
            for nb in n.neighbors:
                if nb.color == color_b and not nb in visited:
                    to_invert.add(nb)
        elif n.color == color_b:
            n.color = color_a
            for nb in n.neighbors:
                if nb.color == color_a and not nb in visited:
                    to_invert.add(nb)


def maximize_color(nodes, color):
    for n in nodes:
        assert(n.color is None)

    colored_nodes = []
    uncolored_nodes = []

    colored_nodes_max = []
    uncolored_nodes_max = []

    for i in range(250):
        random.shuffle(nodes)

        for n in nodes:
            if n.color is None and n.is_feasible(color):
                n.color = color
                colored_nodes.append(n)
            elif n.color is None:
                uncolored_nodes.append(n)

        if len(colored_nodes) > len(colored_nodes_max):
            colored_nodes_max = colored_nodes.copy()
            uncolored_nodes_max = uncolored_nodes.copy()

        for n in nodes:
            n.color = None

        colored_nodes.clear()
        uncolored_nodes.clear()

    for n in colored_nodes_max:
        n.color = color

    return uncolored_nodes_max


def eliminate_color_from_node(node, color_to_eliminate):
    possible_colors = [c for c in range(0, color_to_eliminate)]
    possible_colors.sort(key=lambda c: len(node.get_neighbors_by_color(c)))

    for color_a in possible_colors:

        count_a = node.get_color_count(color_a)
        neighbors_with_color_a = node.get_neighbors_by_color(color_a)

        while neighbors_with_color_a:
            nb = neighbors_with_color_a.pop()
            for color_b in possible_colors:
                if color_a == color_b:
                    continue

                kemp_chain(nb, color_a, color_b)
                count_a_new = node.get_color_count(color_a)

                if count_a_new >= count_a:
                    kemp_chain(nb, color_b, color_a)
                else:
                    count_a = count_a_new
                    neighbors_with_color_a = node.get_neighbors_by_color(color_a)
                    break

        count_a_new = node.get_color_count(color_a)
        assert(count_a == count_a_new)
        if count_a == 0:
            node.color = color_a
            return
    raise ValueError("Wasn't able to eliminate color.")


def eliminate_color(nodes, color_to_eliminate):
    nodes_with_color = [n for n in nodes if n.color == color_to_eliminate]
    for node in nodes_with_color:
        eliminate_color_from_node(node, color_to_eliminate)
    return nodes


def shuffle(nodes, max_color):
    colors = list(range(0, max_color))
    random.shuffle(nodes)
    for node in nodes:
        color = random.choice(colors)
        kemp_chain(node, node.color, color)
    return nodes


def greedy(nodes):
    color = 0
    max_color = {50: 6, 70: 17, 100: 16, 250: 78, 500: 16, 1000: 100}[len(nodes)]

    uncolored_nodes = nodes
    while uncolored_nodes:
        uncolored_nodes = maximize_color(uncolored_nodes, color)
        color += 1

    while color >= max_color:
        try:
            eliminate_color(nodes, color)
            color -= 1
        except ValueError:
            # print("Could not eliminate {}. Shuffle and try again.".format(color))
            shuffle(nodes, color)

    return nodes


def solve_it(input_data):
    color = 0
    nodes = parse(input_data)
    nodes.sort(key=lambda n: len(n.neighbors), reverse=True)

    # greedy_old(nodes, color)
    greedy(nodes)

    return to_output(nodes, input_data)


def to_output(nodes, input_data):
    nodes.sort(key=lambda n: n.index)
    test_nodes = parse(input_data)
    colors = set()

    assert(len(nodes) == len(test_nodes))
    for i in range(len(test_nodes)):
        node = nodes[i]
        test_node = test_nodes[i]
        assert(test_node.index == node.index)
        # This works even if we got rid of the neighbors in the algorithm.
        for neighbor in test_node.neighbors:
            neighbor = nodes[neighbor.index]
            assert(node.color != neighbor.color)
        colors.add(node.color)
    obj = str(len(colors))
    opt = str(0)
    colors = " ".join([str(n.color) for n in nodes])
    return "{} {}\n{}".format(obj, opt, colors)


if __name__ == "__main__":
    file_location = "coloring/data/gc_50_3"
    with open(file_location, 'r') as input_data_file:
        input_data = input_data_file.read()
    print(solve_it(input_data))
