• 貪欲法で有効な彩色を見つける。
• その状態から色を１つ減らして、焼きなまし法やタブーサーチで有効な彩色を見つける。これを繰り返す。

• 診断人さんが使ってたタブーサーチが強かった。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

public class GraphColoring {
    private static final int NUM_TABU_LIST = 75;
    private static final int NG = ((1 << 16) - 1);

    private int numVertexes;
    private int numEdges;
    private IntSet[] nextVertexSet;
    private int usedColors;
    private int[] vertexToColor;

    private int bestUsedColors;
    private int[] bestVertexToColor;

    static final XorShift rng = new XorShift(System.nanoTime());
    static final Watch watch = new Watch();
    private IntSet uncoloredVertexSet;

    private int[] tabuList = new int[NUM_TABU_LIST];
    private int indexOfTabuList = 0;
    private boolean[][] isTabu;

    private int[] colorToSumDegree = new int[256];

    private int[] run(int N, int M, int[] a, int[] b) {
        init(N, M, a, b);
        solve();
        return vertexToColor;
    }

    private void init(int N, int M, int[] a, int[] b) {
        this.numVertexes = N;
        this.numEdges = M;

        Utils.debug("numVertexes", numVertexes, "numEdges", numEdges);

        nextVertexSet = new IntSet[numVertexes];
        for (int i = 0; i < numVertexes; i++) {
            nextVertexSet[i] = new IntSet(numVertexes);
        }
        for (int i = 0; i < numEdges; i++) {
            nextVertexSet[a[i]].add(b[i]);
            nextVertexSet[b[i]].add(a[i]);
        }

        vertexToColor = new int[numVertexes];
        bestVertexToColor = new int[numVertexes];
        for (int i = 0; i < numVertexes; i++) {
            vertexToColor[i] = -1;
            bestVertexToColor[i] = -1;
        }

        bestUsedColors = (int) 1e9;

        uncoloredVertexSet = new IntSet(numVertexes);

        isTabu = new boolean[numVertexes][256];
    }

    private void solve() {
        greedy();
        tabuSearch();
    }

    private void tabuSearch() {
        for (int numIterations = 0;; numIterations++) {
            if ((numIterations & ((1 << 10) - 1)) == 0) {
                if (watch.getSecond() >= 9.5) {
                    loadBest();
                    Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
                    break;
                }
            }
            while (uncoloredVertexSet.size() == 0) {
                saveBest();
                Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
                usedColors--;
                for (int v = 0; v < numVertexes; v++) {
                    if (vertexToColor[v] == usedColors) {
                        uncoloredVertexSet.add(v);
                    }
                }
                initTabuList();
            }

            int vertex = uncoloredVertexSet.get((int) (uncoloredVertexSet.size() * rng.nextDouble()));

            for (int color = 0; color < usedColors; color++) {
                colorToSumDegree[color] = 0;
            }
            for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
                int nextVertex = nextVertexSet[vertex].get(i);
                colorToSumDegree[vertexToColor[nextVertex]] += nextVertexSet[nextVertex].size();
            }

            int bestSumDegree = (int) 1e9;
            int bestColor = -1;
            for (int color = 0; color < usedColors; color++) {
                if (isTabu[vertex][color]) {
                    continue;
                }

                if (colorToSumDegree[color] < bestSumDegree) {
                    bestSumDegree = colorToSumDegree[color];
                    bestColor = color;
                }
            }

            if (bestColor == -1) {
                for (int color = 0; color < usedColors; color++) {
                    if (colorToSumDegree[color] < bestSumDegree) {
                        bestSumDegree = colorToSumDegree[color];
                        bestColor = color;
                    }
                }
            }

            vertexToColor[vertex] = bestColor;
            uncoloredVertexSet.removeValue(vertex);

            for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
                int nextVertex = nextVertexSet[vertex].get(i);
                if (vertexToColor[nextVertex] == bestColor) {
                    vertexToColor[nextVertex] = usedColors;
                    uncoloredVertexSet.add(nextVertex);
                }
            }

            addTabu(vertex, bestColor);

        }
    }

    private void addTabu(int vertex, int color) {
        int tabu = tabuList[indexOfTabuList];
        if (vertex(tabu) != NG) {
            isTabu[vertex(tabu)][color(tabu)] = false;
        }

        tabuList[indexOfTabuList] = encode(vertex, color);
        isTabu[vertex][color] = true;

        indexOfTabuList++;
        if (indexOfTabuList >= NUM_TABU_LIST) {
            indexOfTabuList = 0;
        }
    }

    private void initTabuList() {
        for (int i = 0; i < NUM_TABU_LIST; ++i) {
            int tabu = tabuList[i];
            if (vertex(tabu) != NG) {
                isTabu[vertex(tabu)][color(tabu)] = false;
            }
            tabuList[i] = encode(NG, NG);
        }
    }

    private void greedy() {
        ArrayList<Pair<Integer, Integer>> degreeAndVertexPairs = new ArrayList<>();
        for (int vertex = 0; vertex < numVertexes; vertex++) {
            degreeAndVertexPairs.add(new Pair<Integer, Integer>(-nextVertexSet[vertex].size(), vertex));
        }
        Collections.sort(degreeAndVertexPairs);
        for (int i = 0; i < degreeAndVertexPairs.size(); i++) {
            int vertex = degreeAndVertexPairs.get(i).second.intValue();
            for (int color = 0; color < 256; color++) {
                if (canUse(vertex, color)) {
                    vertexToColor[vertex] = color;
                    break;
                }
            }
        }
        usedColors = calculateUsedColors();
        saveBest();
        Utils.debug("greedy", "usedColors", usedColors, "time", watch.getSecondString());
    }

    private int calculateUsedColors() {
        HashSet<Integer> set = new HashSet<>();
        for (int vertex = 0; vertex < numVertexes; vertex++) {
            set.add(vertexToColor[vertex]);
        }
        return set.size();
    }

    private boolean canUse(int vertex, int color) {
        for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
            int nextVertex = nextVertexSet[vertex].get(i);
            if (vertexToColor[nextVertex] == color) {
                return false;
            }
        }
        return true;
    }

    private void saveBest() {
        if (usedColors < bestUsedColors) {
            bestUsedColors = usedColors;
            for (int i = 0; i < numVertexes; i++) {
                bestVertexToColor[i] = vertexToColor[i];
            }
        }
    }

    private void loadBest() {
        usedColors = bestUsedColors;
        for (int i = 0; i < numVertexes; i++) {
            vertexToColor[i] = bestVertexToColor[i];
        }
    }

    private static final int encode(int vertex, int color) {
        return (vertex << 16) | color;
    }

    private static final int vertex(int v) {
        return v >>> 16;
    }

    private static final int color(int v) {
        return v & ((1 << 16) - 1);
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            String line = br.readLine();
            String[] split = line.split(" ");
            int N = Integer.parseInt(split[0]);
            int M = Integer.parseInt(split[1]);
            int[] a = new int[M];
            int[] b = new int[M];
            for (int i = 0; i < M; i++) {
                line = br.readLine();
                split = line.split(" ");
                a[i] = Integer.parseInt(split[0]);
                b[i] = Integer.parseInt(split[1]);
            }

            GraphColoring gc = new GraphColoring();
            int[] ret = gc.run(N, M, a, b);
            for (int i = 0; i < N; ++i) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

class IntSet {
    private static final int EMPTY = -1;
    private int size;
    private int[] indexToValue;
    private int[] valueToIndex;

    public IntSet(int capacity) {
        this.size = 0;
        indexToValue = new int[capacity];
        valueToIndex = new int[capacity];
        Arrays.fill(valueToIndex, EMPTY);
    }

    public boolean add(int value) {
        if (valueToIndex[value] != EMPTY) {
            return false;
        }
        indexToValue[size] = value;
        valueToIndex[indexToValue[size]] = size;
        size++;
        return true;
    }

    public boolean remove(int index) {
        if (size == 0) {
            return false;
        }
        assert index < size;
        int swap = indexToValue[index];
        indexToValue[index] = indexToValue[size - 1];
        indexToValue[size - 1] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[size - 1]] = EMPTY;

        size--;
        return true;
    }

    public boolean removeValue(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public int get(int index) {
        assert index < size;
        return indexToValue[index];
    }

    public int indexOf(int value) {
        return valueToIndex[value];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        for (; size() > 0;) {
            remove(0);
        }
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
    public T first;
    public S second;

    public Pair(T t, S s) {
        this.first = t;
        this.second = s;
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((first == null) ? 0 : first.hashCode());
            result = prime * result + ((second == null) ? 0 : second.hashCode());
            hash = result;
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair<T, S> other = (Pair<T, S>) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        return true;
    }

    @Override
    public int compareTo(Pair<T, S> o) {
        return first.compareTo(o.first);
    }
}

class Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

class XorShift {
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

    public XorShift(long l) {
        x = (int) l;
    }

    public int nextInt() {
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

}

final class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

}