← 返回题目列表

AtCoder · npcapc_2024_o

O. 新学期

中文机器翻译题面 查看原题

配点 : 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