构造一个菊花图，答案一定小于 $2n$，于是答案一定在区间 $[n,2n)$ 内。

令弧 $i$ 为连接 $a_i$ 和 $b_i$ 的弧，考虑构造一个有 $n$ 个点的图，每个弧都是一个顶点，当且 仅当相应的弧相交时，两个顶点之间有一条边。

显然该图的每个连通分量都是独立的。并且可以证明答案为 $2n$ 减去连通分量的个数。每个连通分量都连成一个菊花图就能达到这个值。

我们只需要证明没有更优的方案。考虑一个新的问题：若原图开始没有边，至少需要添加几条边使得图仍满足要求的性质且所有 相同颜色的点 都被连接。

这个问题的答案仍是 $2n$ 减连通分量个数。

因为属于同一连通分量的弧在原图也属于同一连通分量。

显然这个新问题的答案不小于原问题的答案。接下来我们只需要寻找每个连通分量。可以线段树优化建图。另一种方法是给每种类型随机赋一个哈希值，每个连通分量都是一个异或和为 $0$ 的最小划分。按顺序遍历每个点，记录前缀异或和，当有重复值时就得到了一个新的连通分量。删除掉这些点继续遍历。

注意要输出 $2n−3$ 条边。