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.
$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$ is the sum of weight of tree.
If there are multiple solutions, print any of them.
6 3 8 4 9 2 1 10 5 4 9 2 0
21 4 1 5 2 1 0 0 2 1 3
| No. | Testdata Range | Score |
|---|