CodeEff/ECCO huggingface dataset:
# Original solution
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] != x:
            x_now = x
            while self.p[x_now] != x_now:
                x_now = self.p[x_now]
            self.p[x] = x_now
        return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

N = int(eval(input()))
X, Y = [], []
for i in range(N):
    x, y = list(map(int,input().split()))
    X.append([x, i])
    Y.append([y, i])

X.sort()
Y.sort()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

# Optimized solution
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] != x:
            stack = [x]
            while True:
                top = stack[-1]
                if self.p[top] == top:
                    break
                else:
                    stack.append(self.p[top])
            for v in stack:
                self.p[v] = top
        return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

N = int(eval(input()))
X, Y = [], []
for i in range(N):
    x, y = list(map(int,input().split()))
    X.append([x, i])
    Y.append([y, i])

X.sort()
Y.sort()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)
# Original solution
# UnionFind
#############################################################
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################

N = int(eval(input()))
XY = [list(map(int, input().split())) + [i] for i in range(N)]

X = sorted(XY, key=lambda x: x[0])
Y = sorted(XY, key=lambda x: x[1])

side = []
for i in range(N - 1):
    # iとi+1の距離、iのindex, i+1のindex
    side.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    side.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

ans = 0
side.sort(key=lambda x: x[0])

uf = UnionFind(N)

for cost, i, j in side:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)


# Optimized solution
# UnionFind
#############################################################
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################

N = int(eval(input()))
XY = [list(map(int, input().split())) + [i] for i in range(N)]

X = sorted(XY, key=lambda x: x[0])
Y = sorted(XY, key=lambda x: x[1])

dist = []
for i in range(N - 1):
    # iとi+1の距離、iのindex, i+1のindex
    dist.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    dist.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

ans = 0
dist.sort(key=lambda x: x[0])

uf = UnionFind(N)
# クラスカル法
for cost, i, j in dist:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)
# Original solution
# UnionFind
#############################################################
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################

N = int(eval(input()))
XY = [list(map(int, input().split())) + [i] for i in range(N)]

X = sorted(XY, key=lambda x: x[0])
Y = sorted(XY, key=lambda x: x[1])

dist = []
for i in range(N - 1):
    # iとi+1の距離、iのindex, i+1のindex
    dist.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    dist.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

ans = 0
dist.sort(key=lambda x: x[0])

uf = UnionFind(N)
# クラスカル法
for cost, i, j in dist:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)


# Optimized solution
# UnionFind
#############################################################
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################
import sys
input = sys.stdin.readline

N = int(eval(input()))
XY = [list(map(int, input().split())) + [i] for i in range(N)]

X = sorted(XY, key=lambda x: x[0])
Y = sorted(XY, key=lambda x: x[1])

dist = []
for i in range(N - 1):
    # iとi+1の距離、iのindex, i+1のindex
    dist.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    dist.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

ans = 0
dist.sort(key=lambda x: x[0])

uf = UnionFind(N)
# クラスカル法
for cost, i, j in dist:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)
# Original solution
N = int(eval(input()))
XY = [list(map(int, input().split())) + [i + 1] for i in range(N)]

dist = []

XY.sort()
for i in range(N - 1):
  dist.append((abs(XY[i][0] - XY[i + 1][0]), (XY[i][2], XY[i + 1][2])))
XY.sort(key = lambda x: x[1])
for i in range(N - 1):
  dist.append((abs(XY[i][1] - XY[i + 1][1]), (XY[i][2], XY[i + 1][2])))
dist.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

print(answer)

# Optimized solution
import sys
input = sys.stdin.buffer.readline

N = int(eval(input()))
XY = [list(map(int, input().split())) + [i + 1] for i in range(N)]

dist = []

XY.sort()
for i in range(N - 1):
  dist.append((abs(XY[i][0] - XY[i + 1][0]), (XY[i][2], XY[i + 1][2])))
XY.sort(key = lambda x: x[1])
for i in range(N - 1):
  dist.append((abs(XY[i][1] - XY[i + 1][1]), (XY[i][2], XY[i + 1][2])))
dist.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

print(answer)
# Original solution

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(eval(input()))
points = []
edges = []
for i in range(N):
    x,y = list(map(int, input().split()))
    points.append([i,i,[x,y]])
    for j in range(i):
        edges.append((abs(points[i][2][0] - points[j][2][0]), j, i))
        edges.append((abs(points[i][2][1] - points[j][2][1]), j, i))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)


# Optimized solution

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(eval(input()))
points = []
edges = []
for i in range(N):
    x,y = list(map(int, input().split()))
    points.append([i,i,[x,y]])
points.sort(key=lambda x:x[2][0])
for i in range(N-1):
    edges.append((abs(points[i][2][0] - points[i+1][2][0]), points[i][1], points[i+1][1]))
points.sort(key=lambda x:x[2][1])
for i in range(N-1):
    edges.append((abs(points[i][2][1] - points[i+1][2][1]), points[i][1], points[i+1][1]))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
points.sort()
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)
# Original solution

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] + 1> par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1] + 1
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(eval(input()))
points = []
edges = []
for i in range(N):
    x,y = list(map(int, input().split()))
    points.append([i,i,[x,y]])
points.sort(key=lambda x:x[2][0])
for i in range(N-1):
    edges.append((abs(points[i][2][0] - points[i+1][2][0]), points[i][1], points[i+1][1]))
points.sort(key=lambda x:x[2][1])
for i in range(N-1):
    edges.append((abs(points[i][2][1] - points[i+1][2][1]), points[i][1], points[i+1][1]))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
points.sort()
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)


# Optimized solution
import sys
sys.setrecursionlimit(100000)

def unite(i, j):
    j = get_par(j)
    par[j] = get_par(i)
    return

def get_par(p):
    if par[p] is None:
        return p
    par[p] = get_par(par[p])
    return par[p]

N = int(eval(input()))
points = []
edges = []
for i in range(N):
    x,y = list(map(int, input().split()))
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(i) == get_par(j):
        continue
    unite(i, j)
    cost += c
    count += 1
print(cost)
# Original solution
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n = int(eval(input()))
zahyo = []
for i in range(n):
    x,y = list(map(int,input().split()))
    zahyo.append((x,y))
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    for j in range(i+1,n):
        c = min(abs(zahyo[i][0]-zahyo[j][0]),abs(zahyo[i][1]-zahyo[j][1]))
        edge[j].append((c,i))
        edge[i].append((c,j))
print((prim_heap()))

# Optimized solution
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n = int(eval(input()))
zahyo = []
for i in range(n):
    x,y = list(map(int,input().split()))
    zahyo.append((x,y,i))
xza = sorted(zahyo)
yza = sorted(zahyo,key=lambda x: x[1])
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    c = abs(xza[i][0]-xza[i+1][0])
    edge[xza[i][2]].append((c,xza[i+1][2]))
    edge[xza[i+1][2]].append((c,xza[i][2]))
for i in range(n-1):
    c = abs(yza[i][1]-yza[i+1][1])
    edge[yza[i][2]].append((c,yza[i+1][2]))
    edge[yza[i+1][2]].append((c,yza[i][2]))
print((prim_heap()))
# Original solution
from operator import itemgetter
import heapq
N = int(eval(input()))
X = []
Y = []
for i in range(N):
    x, y = list(map(int, input().split()))
    X.append((x, i))
    Y.append((y, i))
X.sort(key=itemgetter(0))
Y.sort(key=itemgetter(0))
G = [[] for _ in range(N)]
for i in range(N-1):
    G[X[i][1]].append((X[i+1][0]-X[i][0], X[i+1][1]))
    G[X[i+1][1]].append((X[i+1][0]-X[i][0], X[i][1]))
    G[Y[i][1]].append((Y[i+1][0]-Y[i][0], Y[i+1][1]))
    G[Y[i+1][1]].append((Y[i+1][0]-Y[i][0], Y[i][1]))

q = []
heapq.heapify(q)
for elem in G[0]:
    heapq.heappush(q, elem)
used = [False] * N
used[0] = True
ans = 0
while q:
    res = heapq.heappop(q)
    cost, nq = res
    if not used[nq]:
        used[nq] = True
        ans += cost
        for elem in G[nq]:
            heapq.heappush(q, elem)
print(ans)


# Optimized solution
from operator import itemgetter
import heapq
N = int(eval(input()))
X = []
Y = []
for i in range(N):
    x, y = list(map(int, input().split()))
    X.append((x, i))
    Y.append((y, i))
X.sort(key=itemgetter(0))
Y.sort(key=itemgetter(0))

import sys
sys.setrecursionlimit(10**6)


class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False
u = UnionFind(N)
q = []
for i in range(N-1):
    q.append((X[i+1][0]-X[i][0], X[i+1][1], X[i][1]))
    q.append((Y[i+1][0]-Y[i][0], Y[i+1][1], Y[i][1]))
q.sort(key=itemgetter(0))
ans = 0
for elem in q:
    cost, a, b = elem
    if u.union(a, b):
        ans += cost
print(ans)
# Original solution
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from collections import defaultdict
from itertools import chain
from bisect import bisect

N = int(eval(input()))
points = tuple(tuple(map(int,input().split())) for _ in range(N))

ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        if ds.find(i0) != ds.find(i1):
            ds.union(i0,i1)
            yield d
print((sum(it())))

# Optimized solution
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain

N = int(eval(input()))
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        if ds.find(i0) != ds.find(i1):
            ds.union(i0,i1)
            yield d
print((sum(it())))