#T2316. 图着色(Graph Coloring)

图着色(Graph Coloring)

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

板块: Advanced Graph Problems

时限: 1.00 s | 内存: 512 MB

题目描述

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

输入

第一行包含两个整数 nn 和 mm:节点数量和边的数量。节点编号为 1,2,…,n1, 2,\dots, n。

接下来有 mm 行描述边。每行包含两个整数 aa 和 bb:表示节点 aa 与 bb 之间有一条边。

输出

先输出一个整数 kk:最少的颜色数量。

之后输出 nn 个整数 c1,c2,…,cnc_1, c_2,\dots, c_n:各节点的颜色。颜色应满足 1≤ci≤k1 \le c_i \le k。

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

数据范围

1≤n≤161 \le n \le 16 0≤m≤n(n−1)20 \le m \le \frac{n(n-1)}{2}

样例输入

4 4
1 2
2 3
3 4
4 1

样例输出

2
1 2 1 2