AT_npcapc_2024_o New School Term

NPCA 校有 $2N$ 名学生，每位学生被编号为 $1$ 到 $2N$。なぷか君是一名 NPCA 校的老师，现在需要将学生分成两个班级，每个班级恰好 $N$ 人。 此处，班级划分的不满度定义如下： - 对于所有整数 $i(1 \le i \le M)$ 中，学生 $A_i$ 和学生 $B_i$ 属于同一班级的情况，将 $2^i$ 相加，求总和。 请为なぷか君构造一种使不满度最小的班级划分方案。

输入以以下格式从标准输入读入。 > $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

请按如下格式输出。 > $S_1 S_2 \dots S_{2N}$ 这里，$S_i$ 为 `0` 或 `1`，表示学生 $i$ 属于哪一个班级。 如果存在多种满足条件的划分方案，输出任意一种都可以。

## 样例解释 1 将学生 $1$ 与学生 $3$ 分在一组，将学生 $2$ 与学生 $4$ 分在另一组时，不满度的计算如下： - 对于 $i=1$，学生 $1$ 和学生 $3$ 在同一班级。 - 对于 $i=2$，学生 $2$ 和学生 $4$ 在同一班级。 - 对于 $i=3$，学生 $1$ 和学生 $4$ 不在同一班级。 - 对于 $i=4$，学生 $1$ 和学生 $2$ 不在同一班级。 因此，该方案的不满度为 $2^1 + 2^2 = 6$，且该方案为最优。例如输出 `1010` 也是正确的。 如果分组为 `0111`，其不满度为 $4$，但没有满足每组人数相等的条件，因此不合法。 ## 数据范围 - $1 \le N \le 5000$ - $0 \le M \le 10^6$ - $1 \le A_i < B_i \le 2N$ - 若 $i\ne j$，则 $(A_i,B_i)\ne (A_j,B_j)$ - 所有输入值均为整数。 由 ChatGPT 5 翻译