CF1045E Ancient civilizations

在一颗新发现的星球表面（我们将其视为一个平面），探险者在不同的位置发现了两个不同文明的遗迹。他们希望进一步了解这些文明，并需要在部分遗址之间修建道路以便探索。但如往常一样，有一些限制： 1. 同一文明的任意两个遗址之间必须通过唯一的一条道路路径连通。 2. 不同文明的任意两个遗址之间不能有道路相连（探险者不希望在探索过程中混淆不同文明）。 3. 道路必须是直线线段。 4. 由于交叉点的建设成本很高，任何两条道路都不能相交（即，任意两条道路的唯一公共点只能是某个遗址的位置）。 显然，所有遗址的位置在平面上都是不同的点。探险者还发现了一个有趣的信息，或许对你有帮助——没有三个遗址共线！ 请帮助探险者为他们的问题找到一个解决方案，或者报告无法实现。

第一行，一个整数 $n$，表示发现的遗址数量，$1 \leq n \leq 10^3$。 接下来的 $n$ 行，每行包含三个整数 $x, y, c$，表示该遗址的坐标和所属文明编号，$0 \leq x, y \leq 10^4$，$c \in \{0, 1\}$。

第一行输出需要修建的道路数量。 接下来的每一行输出一对遗址的编号（$0$-基编号），表示这两个遗址之间需要修建一条道路。 如果无法满足所有限制条件，输出 “Impossible”。不要输出引号。

由 ChatGPT 4.1 翻译