#P18188. New School Term

New School Term

New School Term

题目描述

NPCA 学校有 2N2N 名学生,编号为 11 到 2N2N。老师 Napuka 需要将他们分成两个班,每个班恰好有 NN 名学生。

给定 MM 对学生 (Ai,Bi)(A_i,B_i),其中 i=1,2,…,Mi=1,2,\ldots,M。如果第 ii 对中的两名学生被分到同一个班,则产生 2i2^i 的不满意度;否则这一对不产生不满意度。

总不满意度为所有这些值之和。请构造一种分班方案,使总不满意度最小。

注意,权值由学生对在输入中的下标决定:第一对的权值是 212^1,第二对的权值是 222^2,以此类推。

输入格式

第一行包含两个整数 N,MN,M。

接下来 MM 行,第 ii 行包含两个整数 Ai,BiA_i,B_i,表示第 ii 对学生。

输出格式

输出一个长度为 2N2N 的字符串 S1S2⋯S2NS_1S_2\cdots S_{2N},其中每个字符均为 00 或 11。

SiS_i 表示第 ii 名学生所在的班。字符串中必须恰好有 NN 个 00 和 NN 个 11,且对应方案的总不满意度必须最小。

如果存在多种最优方案,输出任意一种。

数据范围

  • 1≤N≤50001\le N\le5000;
  • 0≤M≤1060\le M\le10^6;
  • 1≤Ai<Bi≤2N1\le A_i<B_i\le2N;
  • 任意两对学生均不同,即 i≠ji\ne j 时 (Ai,Bi)≠(Aj,Bj)(A_i,B_i)\ne(A_j,B_j);
  • 所有输入值均为整数。

输入只有一组数据,允许 M=0M=0。

样例 1

输入:

2 4
1 3
2 4
1 4
1 2

输出:

0101

样例 1 解释

学生 1,31,3 在一个班,学生 2,42,4 在另一个班。因此前两对学生各自同班,后两对学生各自异班,总不满意度为

21+22=6,2^1+2^2=6,

这是最小值。也可以输出 1010。

虽然 0111 对应的不满意度是 44,但两个班的人数分别为 11 和 33,不满足每班恰好 N=2N=2 人的要求,因此不是合法答案。

样例 2

输入:

3 7
2 5
1 3
4 6
2 6
4 5
2 4
5 6

输出:

001101