P2076 Manhattan Distance Minimum Spanning Tree

This problem is modified from [Library Checker](https://judge.yosupo.jp/problem/manhattanmst), and the [data generator / validator source](https://github.com/yosupo06/library-checker-problems/tree/master/geo/manhattanmst). Note that in the original problem all indices are $0$-indexed, while in this problem all indices are $1$-indexed.

Given $n$ points $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$ in the plane. Consider the complete graph with $n$ nodes. For $1 \le u, v \le n$ and $u \ne v$, there is an edge between nodes $u$ and $v$ with weight $|x_u-x_v|+|y_u-y_v|$. Find a minimum spanning tree of this graph.

The first line contains an integer $n$, the number of points. The next $n$ lines, the $i$-th line contains two integers $(x_i,y_i)$, the coordinates of the $i$-th point.

The first line contains an integer $x$, the sum of edge weights in the minimum spanning tree. Then $(n-1)$ lines follow. The $i$-th line contains two integers $(u_i,v_i)$, representing one edge in the minimum spanning tree. If there are multiple valid answers, you may output any of them.

For $20\%$ of the testdata, $1 \le n \le 1000$. For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $0 \le x_i,y_i \le 10^9$. Translated by ChatGPT 5