AT_abc333_e.[ABC333E] Takahashi Quest

高桥君准备踏上冒险之旅。

在冒险过程中，将会发生 $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$ 的最小值记为 $K_{\min}$。请输出 $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$ 个事件发现的药水，若拾取则输出 1，否则输出 0，用空格分隔。

若存在多种实现 $K_{\min}$ 且不会失败的行为方案，输出任意一种均可。

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq t_i \leq 2\ (1 \leq i \leq N)$
• $1 \leq x_i \leq N\ (1 \leq i \leq N)$
• 输入均为整数

样例解释 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$ 且不会失败的行为方案有多种，输出任意一种均可。

样例解释 2

高桥君必然会在第一次遇到怪物时失败。

由 ChatGPT 4.1 翻译