P14606 [NWRRC 2025] Games of Chess

在象棋城有 $n$ 个朋友和 $n$ 栋房子，都从 $1$ 到 $n$ 编号，其中朋友 $i$ 住在房子 $i$。这些房子通过 $m$ 条双向道路连接，形成一个连通网络。 象棋城还有 $n$ 个虚拟象棋俱乐部，编号从 $1$ 到 $n$。每个朋友必须选择恰好一个俱乐部加入。这些选择不必互不相同，因此有些俱乐部可能没有任何成员。 当朋友 $i$ 举办象棋派对时，所有与朋友 $i$ 属于同一俱乐部且住在与房子 $i$ 直接通过道路连接的房子里的朋友都会参加。如果包括朋友 $i$ 在内的总参加人数是偶数，则该派对被认为是 **成功的**；在这种情况下，他们可以同时下象棋。 请为每个朋友选择一个俱乐部，使得每个朋友的派对都成功，或者报告这是不可能的。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示房子的数量和道路的数量（$2 \le n \le 10^5$；$n - 1 \le m \le 2 \cdot 10^5$）。 接下来的 $m$ 行每行包含两个整数 $u$ 和 $v$，描述房子 $u$ 和 $v$ 之间的双向道路（$1 \le u, v \le n$；$u \ne v$）。任意两栋房子之间最多由一条道路连接。可以通过道路从任何房子到达任何其他房子。 保证所有测试用例的 $n$ 之和不超过 $10^5$，所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果无法为每个朋友分配一个象棋俱乐部使得每个朋友的派对都成功，则输出单个整数 $-1$。 否则，输出 $n$ 个整数 $c_1, c_2, \ldots, c_n$，其中 $c_i$ 是朋友 $i$ 应该加入的象棋俱乐部的编号（$1 \le c_i \le n$）。如果有多个答案，输出其中任意一个。

翻译由 DeepSeek V3 完成