맨해튼 MST

$N$개의 2차원 점이 주어진다. $i$번째 점은 $(x_i, y_i)$이다.

각 $i, j$에 대해 두 점 사이에 가중치가 $|x_i - x_j| + |y_i - y_j|$인 간선을 추가한다.

이 그래프의 MST를 계산한다.

제약 조건

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

$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$는 트리의 가중치 합이다. 해가 여러 개라면 그중 아무거나 출력한다.