Manhattan MST

时间限制: 5 秒

题目描述

给定 $N$ 个二维点。第 $i$ 个点是 $(x_i, y_i)$。

对于每一对 $i, j$，我们在它们之间添加一条边，其权重为 $|x_i - x_j| + |y_i - y_j|$。

计算该图的最小生成树（MST）。

约束条件

• $1 \le N \le 200,000$
• $0 \le x_i, y_i \le 10^9$

输入

输入格式如下：

N
x_0 y_0
x_1 y_1
:
x_{N-1} y_{N-1}

输出

输出格式如下：

X
u_0 v_0
u_1 v_1
:
u_{N-2} v_{N-2}

其中 $X$ 是树的权重之和。如果存在多个解，输出任意一个即可。

6
3 8
4 9
2 1
10 5
4 9
2 0

21
4 1
5 2
1 0
0 2
1 3