Public Judge

pjudge

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

#21672. 【NOIP Round #1】冲塔

Статистика

你是一个冲塔大队的首领,要率领部下进行坚定全面地冲塔。

平面上有 $n$ 个塔,第 $i$ 个塔的位置是 $(x_i,y_i)$ ,且位置两两不同。你可以选择任意若干个塔进行冲塔,但是需要满足两个条件:

  • 为了保证部下的安全返回,同一个横坐标只能冲至多两个塔,同一个纵坐标也只能冲至多两个塔。
  • 为了保证冲塔的全面进行,一个没有被冲的塔必须被夹在两个横坐标相同的、且已经被冲了的塔之间,或是夹在两个纵坐标相同的已经被冲了的塔之间。

构造一个合法的冲塔方案,或判断无解。

输入格式

第一行一个正整数 $n$ 。

接下来 $n$ 行,第 $i$ 行两个整数 $x_i,y_i$ 。

输出格式

如果无解,输出 $-1$ 。

否则输出一行一个长度为 $n$ 的 $01$ 字符串,第 $i$ 个字符为 $1$ 当且仅当你选择冲第 $i$ 个塔。

样例一

input

3
1 1
1 6
1 5

output

110

explanation

每个横坐标和纵坐标都至多只冲了两座塔,且唯一一座没有被冲的塔被夹在了两个横坐标相同的塔之间。

样例二

input

6
1 1
1 2
2 1
2 2
3 1
3 2

output

110011

样例三、四

见下发文件。

数据范围与提示

本题捆绑测试。

对于所有数据,保证 $1\le x_i,y_i,n\le 10^6$ 。

子任务编号 $n\le$ 特殊性质 分值
$1$ $3$ $ $ $5$
$2$ $16$ $ $ $11$
$3$ $10^6$ 存在 $a,b$ 使得 $n=ab$ ,且 $1\le x_i\le b,1\le y_i\le a$ 。 $7$
$4$ $10^6$ 每个横坐标上至多有两座塔。 $6$
$5$ $5000$ $ $ $31$
$6$ $10^5$ $ $ $21$
$7$ $10^6$ $ $ $19$