曼哈顿最小生成树

【题目描述】

给定 $N$ 个二维平面上的点，第 $i$ 个点为 $(x_i, y_i)$。

对每一对 $i, j$，在它们之间连一条边，边权为 $|x_i - x_j| + |y_i - y_j|$。

求这个图的最小生成树。

【输入】

$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

【数据范围】

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

【来源】

Library Checker（yosupo06） manhattanmst

本题为 special judge（输出任意合法解），暂不可本地评测。