CF1070L Odd Federalization

Berland 有 $n$ 个城市，其中一些城市之间通过道路相连。每条道路都是双向的，连接两个不同的城市，并且任意两座城市之间至多只有一条道路相连。 Berland 的总统决定将国家划分为 $r$ 个州，使得每个城市恰好属于这 $r$ 个州中的一个。 划分完成后，每条道路要么连接同一州的两个城市，要么连接不同州的两个城市。我们称连接同一州内两个城市的道路为“内部道路”。 总统不喜欢奇数的人、奇数的城市和奇数的数字，因此他希望划分方式满足：每个城市连接的“内部道路”数量都是偶数。 请你帮助总统找到满足条件的最小 $r$，并给出一种划分方案。

输入包含一个或多个测试用例。第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例，测试用例之间相互独立，互不影响。 每个测试用例之间用一个空行分隔。每个测试用例的第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \le n \le 2000$，$0 \le m \le 10000$），分别表示城市数量和道路数量。接下来的 $m$ 行，每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示第 $i$ 条道路连接城市 $x_i$ 和 $y_i$。任意一对城市之间至多只有一条道路。 所有测试用例中 $n$ 的总和不超过 $2000$，$m$ 的总和不超过 $10000$。

对于每个测试用例，首先输出一行一个整数 $r$，表示满足条件的最小州数。接下来一行输出 $n$ 个用空格分隔的整数，范围为 $1$ 到 $r$，第 $j$ 个数表示第 $j$ 个城市所属的州编号。如果有多种方案，输出任意一种均可。

由 ChatGPT 4.1 翻译