链接: https://cses.fi/problemset/task/3308

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个含有 $n$ 个节点和 $m$ 条边的简单图。你的任务是使用尽可能少的颜色为每个节点着色，使得没有一条边连接两个同色的节点。

输入

第一行包含两个整数 $n$ 和 $m$：节点数量和边的数量。节点编号为 $1, 2,\dots, n$。

接下来有 $m$ 行描述边。每行包含两个整数 $a$ 和 $b$：表示节点 $a$ 与 $b$ 之间有一条边。

输出

先输出一个整数 $k$：最少的颜色数量。

之后输出 $n$ 个整数 $c_1, c_2,\dots, c_n$：各节点的颜色。颜色应满足 $1 \le c_i \le k$。

你可以输出任意一组合法解。

数据范围

$1 \le n \le 16$ $0 \le m \le \frac{n(n-1)}{2}$

样例输入

4 4
1 2
2 3
3 4
4 1

样例输出

2
1 2 1 2