Description

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.

Input Format

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.

Output Format

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.

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

21
5 2
6 3
1 2
3 1
4 1

Hint

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