TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

Given $N$ 2D-points. $i$-th is $(x_ i, y_ i)$.

For each $i, j$, we add edge between them and whose weight is $|x_ i - x_ j| + |y_ i - y_ j|$.

Calculate MST of this graph.

Input Format

$N$
$x_ 0$ $y_ 0$
$x_ 1$ $y_ 1$
:
$x_ {N - 1}$ $y_ {N - 1}$

Output Format

$X$
$u_ 0$ $v_ 0$
$u_ 1$ $v_ 1$
:
$u_ {N - 2}$ $v_ {N - 2}$

$X$ is the sum of weight of tree.
If there are multiple solutions, print any of them.

Sample Input 1

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

Sample Output 1

21
4 1
5 2
1 0
0 2
1 3

Hints

  • $1 \leq N \leq 200,000$
  • $0 \leq x_ i, y_ i \leq 10^ 9$

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152