CF1070L.Odd Federalization

Berland has $n$ cities, some of which are connected by roads. Each road is bidirectional, connects two distinct cities and for each two cities there's at most one road connecting them.

The president of Berland decided to split country into $r$ states in such a way that each city will belong to exactly one of these $r$ states.

After this split each road will connect either cities of the same state or cities of the different states. Let's call roads that connect two cities of the same state "inner" roads.

The president doesn't like odd people, odd cities and odd numbers, so he wants this split to be done in such a way that each city would have even number of "inner" roads connected to it.

Please help president to find smallest possible $r$ for which such a split exists.

伯兰德有 $n$ 座城市，其中一些城市由道路连接。每条道路都是双向的，连接两座不同的城市，且任意两座城市之间至多只有一条道路。

伯兰德总统决定将全国划分为 $r$ 个州，使得每座城市恰好属于这 $r$ 个州中的一个。

划分完成后，每条道路要么连接同一州内的两座城市，要么连接不同州的两座城市。我们将连接同一州内两座城市的道路称为“内部”道路。

总统不喜欢奇数的人、奇数的城市以及奇数，因此他希望该划分满足：每座城市所连的“内部”道路数量均为偶数。

请帮助总统找出满足条件的最小可能的 $r$ 值。

The input contains one or several test cases. The first input line contains a single integer number $t$ — number of test cases. Then, $t$ test cases follow. Solve test cases separately, test cases are completely independent and do not affect each other.

Then $t$ blocks of input data follow. Each block starts from empty line which separates it from the remaining input data. The second line of each block contains two space-separated integers $n$, $m$ ($1 \le n \le 2000$, $0 \le m \le 10000$) — the number of cities and number of roads in the Berland. Each of the next $m$ lines contains two space-separated integers — $x_i$, $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$), which denotes that the $i$-th road connects cities $x_i$ and $y_i$. Each pair of cities are connected by at most one road.

Sum of values $n$ across all test cases doesn't exceed $2000$. Sum of values $m$ across all test cases doesn't exceed $10000$.

输入包含一个或多个测试用例。第一行输入为一个整数 $t$，表示测试用例的数量。随后是 $t$ 个测试用例。请分别求解各个测试用例，各测试用例完全独立，互不影响。

接下来是 $t$ 个输入数据块。每个数据块以一个空行开头，用于将其与其余输入数据分隔开。每个数据块的第二行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \le n \le 2000$，$0 \le m \le 10000$），分别表示 Berland 国家的城市数量和道路数量。接下来的 $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$。

For each test case first print a line containing a single integer $r$ — smallest possible number of states for which required split is possible. In the next line print $n$ space-separated integers in range from $1$ to $r$, inclusive, where the $j$-th number denotes number of state for the $j$-th city. If there are multiple solutions, print any.

对于每个测试用例，首先输出一行，包含一个整数 $r$ —— 满足要求的划分所需的最小状态数。
接下来一行输出 $n$ 个用空格分隔的整数，每个整数的取值范围为 $1$ 到 $r$（含端点），其中第 $j$ 个数表示第 $j$ 个城市的所属状态编号。
若存在多种解法，输出任意一种即可。