P13811 [CERC 2022] Greedy Drawers

Janko 桌子上有 $N$ 本矩形笔记本。第 $i$ 本笔记本的边长为 $A_i$ 和 $B_i$。桌子旁边有一个由 $N$ 个抽屉组成的柜子，每个抽屉也是矩形，但尺寸可能不同。第 $j$ 个抽屉的宽为 $X_j$，深为 $Y_j$。Janko 想把每本笔记本放进一个抽屉。他可以旋转笔记本，但必须让笔记本的边与抽屉的边平行。只有当笔记本的每条边都不超过抽屉对应边的长度时，笔记本才能放进抽屉。 Janko 决定采用如下分配笔记本到抽屉的流程：对于每本笔记本，他会计算它可以放进多少个抽屉。同样地，他会计算每个抽屉可以放进多少本笔记本。然后，他会选择“可选项最少”的对象（笔记本或抽屉）。如果该对象没有可选项，流程失败。如果有多个对象的可选项数量相同且最少，则随机选择一个。他会将该对象随机分配给一个可选项。如果选中的是笔记本，则将其随机分配到一个能放下它的抽屉；如果选中的是抽屉，则将其随机分配给一个能放进它的笔记本。分配后，移除这对笔记本和抽屉，重复该流程直到所有笔记本都被分配到抽屉。 Metka 听说了 Janko 的分配方法，认为这种方法有缺陷，可能无法成功完成分配。请你编写一个程序，读入笔记本和抽屉的数量 $N$，输出一组笔记本和抽屉的尺寸，使得 Janko 的随机贪心方法不一定能找到全部笔记本到抽屉的分配方案，尽管实际上存在一种可行的分配方式。

第一行包含一个整数 $N$，表示笔记本和抽屉的数量。

首先输出 $N$ 行，每行两个用空格分隔的整数 $A_i$ 和 $B_i$，表示第 $i$ 本笔记本的边长。 接下来输出一个空行，然后输出 $N$ 行，每行两个用空格分隔的整数 $X_j$ 和 $Y_j$，表示第 $j$ 个抽屉的尺寸。 所有尺寸均为 $1$ 到 $1000$ 之间的整数。

### 说明 注意，所给的样例输入输出是错误的。输入不满足 $150 \leq N$ 的约束。 在第一个样例中，只有一本笔记本且无法放进唯一的抽屉，因此不存在可行分配。 在第二个样例中，Janko 的方法可以成功分配所有笔记本到抽屉。首先会选择最后一本笔记本（$6 \times 1$）或第一个抽屉（$2 \times 7$），并将其分配给另一个，因为它们都只有一个可选项。此后剩下的笔记本都能放进剩下的抽屉，因此任意分配都可以。 ### 评测 评测时，我们会对你的数据运行 Janko 的随机贪心方法。注意，必须存在一种将所有笔记本分配到抽屉的方案，否则你的输出会被判为错误。你的方案将在 20 个测试用例上评测，Janko 的方法在每个用例上都必须失败。对于每个测试用例，我们会用固定的随机种子运行 Janko 的方法一次。 ### 输入范围 - $150 \leq N \leq 250$ 由 ChatGPT 4.1 翻译