P11515 [CCO 2024] Pizza Party

翻译自 [CCO](https://cemc.uwaterloo.ca/resources/past-contests?contest_category=80) 的 [2024P2题](https://dmoj.ca/problem/cco24p2)。

Troy 正在完善他最新的计划——“HackCCO”！大家都知道，黑客马拉松最大的吸引力就是免费的食物。因此，为了确保“HackCCO”取得空前的成功，Troy 订购了一辆装满 $n$ 份披萨的大车，其中从车的顶部往下数第 $i$ 份披萨的风味是 $a_i$。 披萨车到达后，Troy 需要将它们按照一定的数量堆放在一张长桌上。为此，他从车顶部逐个取下披萨，并将它们放在桌上，每次要么将披萨放在另一堆披萨的顶部，要么在桌上形成新的堆叠。 饥饿的 HackCCO 参与者们排成一排，依次从桌上取披萨。特洛伊知道队伍中第 $i$ 个人最喜欢的披萨口味是 $b_i$。当第 $i$ 个人走到餐桌前时，如果他们在任何一堆顶部看到他们喜欢的口味的比萨，他们会随机拿走其中任意一个。否则，他们什么都不会拿，会饿着肚子离开餐桌。 Troy 不想让任何人饿着离开餐桌。因此，他请你帮助他找到一种将比萨放在餐桌上的排列方式，使得没有人会饿着离开。此外，在所有这样的排列方式中，Troy 想让你找到一个在餐桌上创建最小数量的堆放的排列方式（毕竟，餐桌只能这么长）。帮助他找到这样的排列方式，或者确定这是不可能的！

第一行一个正整数 $n$。 第二行 $n$ 个正整数 $a_1, a _ 2, \ldots, a _ n$。 第三行 $n$ 个正整数 $b _ 1, b _ 2, \ldots, b _ n$。

如果不可能按期望来排列披萨，则输出 `-1`。 否则，输出应该由三行组成。在第一行输出一个整数 $K$，表示最小堆数。在第二行输出 $N$ 个空格分隔的整数 $c_1 \sim c_n$（$1\le c_i \le k$），表示第 $i$ 个披萨应该放在第 $c_i$ 堆上。 在第三行输出 $N$ 个空格分隔的整数 $d_1\sim d_N$（$1\le d_i\le K$），表示第 $i$ 个排队的人从第 $d_i$ 堆里拿披萨。第 $i$ 个人拿的披萨需要满足他们的口味需求。

### 数据范围 | Subtask | 分数 | 约束 | | :----------: | :----------: | :----------: | | Subtask $1$ | $12$ | $1 \le n \le 10^6$，$1 \le a_i,b_i \le 2$ | | Subtask $2$ | $16$ | $1\le n \le 5000$，保证 $a_i$ 互不相同 | | Subtask $3$ | $20$ | $1 \le n \le 10^6$，保证 $a_i$ 互不相同 | | Subtask $4$ | $24$ | $1\le n \le 5000$ | | Subtask $5$ | $28$ | $1 \le n \le 10^6$ | ### 说明 出题人表明原题中的 Subtask $4$ 和 Subtask $5$ 可能没有正确解法，故不对 Subtask $4$ 和 Subtask $5$ 进行评测，故该题满分为 $48$ 分。 Subtask $0$ 为样例。 ### 样例解释 #1  上图是桌子上披萨的排列示意图，红色、黄色、蓝色盒子分别代表口味 $1$、$2$ 和 $3$ 的披萨。