配点 : 100 点
問題文
NPCA学校有 有 2N 名学生,每个学生有 它的顺序为 1 到 2N 。 Napuka 是 NPCA 学校的一名老师,他很照顾他的学生。 N 一次一个人 2 我们决定将其分为两类。
这里,对分类的不满意程度定义如下。
- 整数 i(1 \le i \le M) 学生中 A_i 和学生 B_i 对于所有同班同学 2^i 的总和
对于纳普卡君,我们创建了一种将不满程度降到最低的分类方法。 1 请构建一个。
制約
- 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)
- 所有输入值均为整数
入力
输入将以以下格式从标准输入给出。
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
2 4 1 3 2 4 1 4 1 2
出力例 1
0101
生徒 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 但是,N 不满足条件,因为没有为每个人划分班级。
入力例 2
1 0
出力例 2
01
入力例 3
3 7 2 5 1 3 4 6 2 6 4 5 2 4 5 6
出力例 3
011010