4167. 「CCO 2024」Pizza Party

题目描述

译自 CCO 2024 Day1 T2「Pizza Party」。

Troy 正在筹备他最新的项目——黑客松（HackCCO）！众所周知，任何黑客松活动的最大吸引力之一就是免费食物。为了确保黑客松的空前成功，Troy 订购了一辆装得满满的推车，上面摞着足足 $N$ 个披萨，从上往下第 $i$ 个披萨的口味是 $a_i$。

推车到达后，Troy 需要把这些披萨整理成若干摞放在长桌子上。他需要逐个从推车顶端取走披萨放到桌子上，每次可以选择把披萨放在现有某摞披萨的上面，或者在桌子上新建一摞。

$N$ 个饥肠辘辘的黑客松参与者排队依次从桌子上取披萨。Troy 知道排队第 $i$ 个人喜欢的披萨口味是 $b_i$。当第 $i$ 个人走到桌子旁时，如果他们看到摞在最上面的披萨中有他们喜欢的口味，他们就会随机拿走其中一个。如果没有他们喜欢的口味，他们就会空手而归。

当然，饥饿的程序员可不是快乐的程序员，所以 Troy 不想让任何人饿着肚子离开。因此，他需要你的帮助，找到一种摆放披萨的方法，让所有人都能吃到喜欢的口味。同时，在所有满足条件的方案中，Troy 还希望找到一种能使桌子上的摞数最少的方法（毕竟桌子也不是无限长的）。帮他找到这样的方案，或者告诉他这根本不可能做到！

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个用空格隔开的整数 $a_1, \ldots, a_N$ $(1 \leq a_i \leq N)$，表示从上往下第 $i$ 个披萨的口味。

第三行包含 $N$ 个用空格隔开的整数 $b_1, \ldots, b_N$ $(1 \leq b_i \leq N)$，表示排队第 $i$ 个参与者喜欢的披萨口味。

输出格式

如果无法找到满意的披萨摆放方式，请输出 $-1$。

否则，你的输出应该包含三行。第一行输出 $K$，即所需的最小摞数。第二行输出 $N$ 个用空格隔开的整数 $c_1, \ldots, c_N$ $(1 \leq c_i \leq K)$，表示第 $i$ 个披萨应该放在编号为 $c_i$ 的摞上。第三行输出 $N$ 个用空格隔开的整数 $d_1, \ldots, d_N$ $(1 \leq d_i \leq K)$，表示排队第 $i$ 个人从编号为 $d_i$ 的摞上拿取披萨。当第 $i$ 个参与者走到桌子旁时，该摞最上面的披萨口味必须是 $b_i$。

样例 1

输入

7
1 2 3 2 2 1 3
2 3 1 2 3 2 1

输出

2
1 2 1 2 1 2 2
1 2 2 2 1 2 1

上图展示了一种披萨的摆放方式，红色、黄色、蓝色分别代表口味 $1,2,3$ 的披萨。

样例 2

输入

2
1 2
1 1

输出

-1

数据范围与提示

子任务 4 与子任务 5 暂时未知是否可解决。因此，我们只评测前三个子任务。