K度图的着色 K-Graph Oddity

#### 题目描述 给出一个结点数为奇数的无向图. 根据定义, 一个结点的度数即为它连接边的条数. 在给出的图中每一个结点的度数都不超过一个最小奇数 k. 你需要使用最多 k 种不同的颜色为图着色, 使得每个相邻结点的颜色都不同. 下面给出了 2 个图. 第一个图有 3 个结点, 第二个图有 7 个结点. 在两个图中, 任意一个结点的度数都不超过 3 并且都使用 3 种颜色着色.  #### 输入格式 输入包含多组数据, 每组数据间用一个空行隔开, 每组数据格式如下: 第一行为两个正整数 n (3 ≤ n ≤ 9999, n 为奇数), m (2 ≤ m ≤ 100000), 分别表示图的结点数和边数.接下来 m 行每行 2 个正整数 ai, bi (1 ≤ ai, bi ≤ n), 表示 ai, bi 两个结点之间有一条边. 输入保证图是连通的, 且没有重边和自环. #### 输出格式 每组数据之间用一个空行隔开, 每组数据格式如下: 第一行输出奇数 k 的最小值使得每个结点的度数不超过 k. 接下来 n 行每行一个正整数 ci (1 ≤ ci ≤ k), 表示第 i 个结点的颜色.相邻两个结点的颜色必须不同. 若有多个可能的答案可以任意输出一个, 输入保证至少有一个答案.

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4488 [PDF](https://uva.onlinejudge.org/external/16/p1613.pdf)