在一颗新发现的行星(我们用飞机建模)的表面上,探险家在不同地点发现了两种不同文明的遗迹。他们希望更多地了解这些文明,并探索在一些地点之间修建道路所需的区域。但与往常一样,有一些限制:
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$$$ 的索引)。
如果不可能修建满足所有限制的道路,请打印“不可能”。您不应打印引号。
示例
输入 #1
5 0 0 1 1 0 0 0 1 0 1 1 1 3 2 0
输出 #1
3 1 4 4 2 3 0