유클리드 MST

$N$개의 2D차원 점이 주어진다. $i$번째 점은 $(x _ i, y _ i)$이다.

각 $i$ , $j$에 대해 두 점 사이에 가중치가 $\sqrt{(x _ i - x _ j)^2 + (y _ i - y _ j)^2}$인 간선을 추가한다.

이 그래프의 최소 스패닝 트리를 구한다.

제약 조건

• $1 \leq N \leq 200000$
• $|x _ i|, |y _ i| \leq 10000$

$N$
$x _ 0$ $y _ 0$
$x _ 1$ $y _ 1$
:
$x _ {N - 1}$ $y _ {N - 1}$

$u _ 0$ $v _ 0$
$u _ 1$ $v _ 1$
:
$u _ {N - 2}$ $v _ {N - 2}$

최소 스패닝 트리의 간선 양 끝점에 해당하는 점의 인덱스 $u _ i$ , $v _ i$ 쌍을 모두 $N-1$개 출력한다.

해가 여러 개라면 그중 아무거나 출력한다.