高桥君的冒险

题目描述

高桥君将要踏上冒险之旅。

在冒险过程中,会发生 $N$ 个事件。 第 $i$ 个事件 $(1\leq i\leq N)$ 由整数对 $(t _ i,x _ i)$ $(1\leq t _ i\leq 2,1\leq x _ i\leq N)$ 表示,内容如下:

如果 $t _ i=1$,他找到一瓶类型为 $x _ i$ 的药水。他可以选择捡起它,也可以丢弃它。

如果 $t _ i=2$,他遇到一只类型为 $x _ i$ 的怪物。如果他有类型为 $x _ i$ 的药水,就可以使用一瓶来打败怪物。如果他没有打败它,就会被击败。

判断他能否在不被击败的情况下打败所有怪物。

如果不能打败所有怪物,输出 -1。

否则,设 $K$ 为冒险过程中某一时刻他持有的药水数量的最大值。 设 $K _ {\min}$ 为在所有不会被击败的策略中 $K$ 的最小值。 输出 $K _ {\min}$ 的值,以及高桥君实现 $K _ {\min}$ 的行动。

输入格式

输入按以下格式从标准输入给出:

$N$
$t _ 1$ $x _ 1$
$t _ 2$ $x _ 2$
$\vdots$
$t _ N$ $x _ N$

输出格式

如果高桥君无法打败所有怪物,输出 -1。 如果能够,在第一行输出 $K _ {\min}$ 的值,在第二行按升序对每个满足 $t _ i=1$ 的 $i$ 输出一个数字:若捡起第 $i$ 个事件找到的药水则输出 1,否则输出 0,用空格分隔。 如果有多个行动序列能够实现 $K _ {\min}$ 并完成冒险且不被击败,可以输出任意一个。

样例

13
1 2
1 3
1 1
1 3
1 2
2 3
1 3
1 3
2 3
1 3
2 2
2 3
2 1

3
1 1 1 0 0 1 0 1

样例输出对应的行动如下:

按顺序找到类型 $2,3,1$ 的药水。全部捡起。

按顺序找到类型 $3,2$ 的药水。均不捡起。

遇到类型为 3 的怪物。使用一瓶类型为 3 的药水将其打败。

找到一瓶类型为 3 的药水。捡起它。

找到一瓶类型为 3 的药水。不捡起它。

遇到类型为 3 的怪物。使用一瓶类型为 3 的药水将其打败。

找到一瓶类型为 3 的药水。捡起它。

遇到类型为 2 的怪物。使用一瓶类型为 2 的药水将其打败。

遇到类型为 3 的怪物。使用一瓶类型为 3 的药水将其打败。

遇到类型为 1 的怪物。使用一瓶类型为 1 的药水将其打败。

在这个行动序列中,$K$ 的值为 3。

不存在 $K\leq 2$ 时避免被击败的方法,因此所求的 $K _ {\min}$ 为 3。 存在多个满足 $K=3$ 且能避免被击败的行动序列,可以输出其中任意一个。

4
2 3
1 4
2 1
1 2

-1

他会无可避免地被遇到的第一只怪物打败。

30
1 25
1 2
1 10
1 18
2 18
1 11
2 11
1 21
1 6
2 2
2 10
1 11
1 24
1 11
1 3
1 2
1 18
2 25
1 8
1 10
1 11
2 18
2 10
1 10
2 2
1 24
1 10
2 10
1 25
2 6

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

数据范围

• $1\leq N\leq2\times10^5$
• $1\leq t _ i\leq2\ (1\leq i\leq N)$
• $1\leq x _ i\leq N\ (1\leq i\leq N)$
• 输入中的所有值均为整数。

提示

答案不唯一,输出任意合法解即可。