There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.
You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.
Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

-----Constraints-----
 - 2 ≤ N ≤ 10^5
 - 0 ≤ x_i,y_i ≤ 10^9
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_N y_N

-----Output-----
Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

-----Sample Input-----
3
1 5
3 9
7 8

-----Sample Output-----
3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Difficulty: interview

Starter code:

Solutions:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
                self.size[x] += self.size[y]
                self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def siz(self, x):
        x = self.find(x)
        return self.size[x]


N = int(input())
UF = UnionFind(N)
X = []
Y = []
Branch = []
for i in range(N):
    x, y = list(map(int, input().split()))
    X.append((x, i))
    Y.append((y, i))
X.sort()
Y.sort()
for X1, X2 in zip(X, X[1:]):
    Branch.append((X2[0] - X1[0], X1[1], X2[1]))
for Y1, Y2 in zip(Y, Y[1:]):
    Branch.append((Y2[0] - Y1[0], Y1[1], Y2[1]))
Branch.sort()

# 負のとき size, 非負のとき parent
par = [-1] * N
ans = 0
for c, a, b in Branch:
    if N <= 1:
        break
    if not UF.same_check(a, b):
        UF.union(a, b)
        ans += c
        N -= 1

print(ans)



import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return list(map(int, input().split()))
def read_index(): return [int(x) - 1 for x in input().split()]
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N
    
    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a
        
        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


def main():
    N = int(input())
    X = []
    Y = []
    for i in range(N):
        a, b = read_values()
        X.append((a, i))
        Y.append((b, i))
    
    X.sort()
    Y.sort()

    Q = []
    for i in range(N - 1):
        heapq.heappush(Q, (X[i + 1][0] - X[i][0], (X[i][1], X[i + 1][1])))
        heapq.heappush(Q, (Y[i + 1][0] - Y[i][0], (Y[i][1], Y[i + 1][1])))

    res = 0
    uf = UF(N)
    while uf.num_group != 1:
        c, (a, b) = heapq.heappop(Q)

        if not uf.is_pair(a, b):
            res += c
            uf.make_pair(a, b)

    print(res)


def __starting_point():
    main()


__starting_point()

class UnionFind:
    def __init__(self, n):
        self.v = [-1] * n

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.v[self.find(x)]


def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    N = int(input())

    ps = []
    xs = set()
    ys = set()
    for i in range(N):
        x, y = list(map(int, input().split()))
        ps.append((x, y))
        xs.add(x)
        ys.add(y)

    xs = tuple(sorted(xs))
    ys = tuple(sorted(ys))

    dx = {e: i for i, e in enumerate(xs)}
    dy = {e: i for i, e in enumerate(ys)}

    uf = UnionFind(N * 2)
    for x, y in ps:
        uf.unite(dx[x], dy[y] + N)

    def make_edges(xs, start):
        xes = []
        for i, (x0, x1) in enumerate(zip(xs, xs[1:]), start=start):
            xes.append((abs(x1 - x0), i, i + 1))
        return xes

    xes = make_edges(xs, start=0)
    yes = make_edges(ys, start=N)

    # Kruskal
    # 最小コストの辺から順に使用する
    # 同じ連結成分に属していればつながない(閉路を作らない)
    # コスト昇順ソート済みの辺リストを使用する
    ret = 0
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


def __starting_point():
    main()

__starting_point()

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


# Union Find（経路圧縮有）
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 親が同じか判別
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 根を繋ぎ直す
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 親が同じか判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 連結成分の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


def kruskal(max_node, edge):
    """
    :param max_node: UnionFind木に渡す頂点数です
    :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
    :return: 最小全域木のコストの和
    """
    edge.sort()
    uf = UnionFind(max_node)
    cost_sum = 0
    for cost, node1, node2 in edge:
        if not uf.same(node1, node2):
            cost_sum += cost
            uf.union(node1, node2)
    return cost_sum


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

    def calc(L):
        for i in range(n - 1):
            cost = abs(L[i][1] - L[i + 1][1])
            edge.append((cost, L[i][0], L[i + 1][0]))

    edge = []
    X.sort(key=lambda x: x[1])
    Y.sort(key=lambda x: x[1])
    calc(X)
    calc(Y)
    print((kruskal(n, edge)))


def __starting_point():
    resolve()

__starting_point()

n = int(input())
l = []
for i in range(n):
    x,y = list(map(int,input().split()))
    l.append([x,y,i])

lx = sorted(l)
ly = sorted(l, key=lambda x: x[1])

e = []
for i in range(n-1):
    e.append([lx[i+1][0]-lx[i][0],lx[i+1][2],lx[i][2]])
    e.append([ly[i+1][1]-ly[i][1],ly[i+1][2],ly[i][2]])


class Unionfind:
    
    def __init__(self,n):
        self.uf = [-1]*n

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

    def same(self,x,y):
        return self.find(x) == self.find(y)

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
s = set()
u = Unionfind(n)
count = 0
e.sort()
for i in e:
    if not u.same(i[1],i[2]):
        u.union(i[1],i[2])
        s.add(i[1])
        s.add(i[2])
        count += i[0]
print(count)


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
import heapq    
    
n = int(input())
a = []
b = []
for i in range(n):
    x,y= map(int, input().split())
    a.append((x,y,i))
    b.append((y,x,i))
a.sort()
b.sort()
edgea = []
edgeb = []
for i in range(n-1):
    edgea.append((a[i+1][0]-a[i][0],a[i][2],a[i+1][2]))
    edgeb.append((b[i+1][0]-b[i][0],b[i][2],b[i+1][2]))
edge = edgea+edgeb
heapq.heapify(edge)

uf = UnionFind(n)
ans = 0
while len(edge):
    x,y,z = heapq.heappop(edge)
    if not uf.same(y,z):
        ans += x
        uf.union(y,z)
print(ans)

"""Minimum spanning tree with Kruskal's algorithm"""
import sys


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self._root_table) if x == i]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


input = sys.stdin.readline


def main():
    N = int(input())
    cities, xs, ys = [], [], []
    for i in range(N):
        x, y = list(map(int, input().split()))
        cities.append((x, y))
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()
    xd, yd = [], []
    for i in range(1, N):
        x1, c1 = xs[i - 1]
        x2, c2 = xs[i]
        if x2 - x1 <= abs(cities[c1][1] - cities[c2][1]):
            xd.append((x2 - x1, c1, c2))
        y1, c1 = ys[i - 1]
        y2, c2 = ys[i]
        if y2 - y1 < abs(cities[c1][0] - cities[c2][0]):
            xd.append((y2 - y1, c1, c2))
    xd.sort()

    uf = UnionFind(N)
    cost = 0
    merged_cnt = 0
    for d1, c1, c2 in xd:
        if not uf.same(c1, c2):
            uf.union(c1, c2)
            cost += d1
            merged_cnt += 1
            if merged_cnt == N - 1:
                break
    print(cost)


def __starting_point():
    main()

__starting_point()

import sys
import collections
sys.setrecursionlimit(10 ** 8)

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class UnionFind:
    def __init__(self, size):
        self.par = [i for i in range(size)]
        self.rank = [0] * size

    def find(self, x):
        if self.par[x] == x: return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return

    def same(self, x, y): return self.find(x) == self.find(y)

def main():
    N = Z()
    Cs = [ZZ()+[i] for i in range(N)]
    X = sorted(Cs)
    Y = sorted(Cs, key=lambda x:x[1])
    es = []
    for i in range(N-1):
        c = X[i+1][0] - X[i][0]
        u, v = X[i][2], X[i+1][2]
        es.append([c, u, v])
    for i in range(N-1):
        c = Y[i+1][1] - Y[i][1]
        u, v = Y[i][2], Y[i+1][2]
        es.append([c, u, v])
    es.sort()
    uf = UnionFind(N)
    output = 0
    for i in range(len(es)):
        c, u, v = es[i]
        if not uf.same(u, v):
            uf.unite(u, v)
            output += c
    print(output)

    return

def __starting_point():
    main()

__starting_point()

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N, *XY = list(map(int, read().split()))
    X = list(zip(XY[::2], list(range(N))))
    Y = list(zip(XY[1::2], list(range(N))))

    X.sort()
    Y.sort()

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

    edge.sort()

    uf = UnionFind(N)
    ans = 0
    for d, s, t in edge:
        if not uf.same(s, t):
            uf.union(s, t)
            ans += d

    print(ans)
    return


def __starting_point():
    main()

__starting_point()

from heapq import heappush, heappop, heapify
N = int(input())

X = []
Y = []
for n in range(N):
    x,y = list(map(int,input().split()))
    X.append([x,n])
    Y.append([y,n])#座標、頂点番号
X.sort()
Y.sort()

#隣接リスト。大きさではなく町番号で記録
adj = list([] for _ in range(N))

#隣接リストを作る
for n in range(N-1):#X[n]は下からn番目に大きい数
    costx = X[n+1][0] - X[n][0]
    #お互いの隣接リストにコストと相手の番号を追加
    adj[X[n+1][1]].append([costx,X[n][1]])#コストと相手の番号
    adj[X[n][1]].append([costx,X[n+1][1]])
    
    costy = Y[n+1][0] - Y[n][0]
    adj[Y[n+1][1]].append([costy,Y[n][1]])#コストと相手の番号
    adj[Y[n][1]].append([costy,Y[n+1][1]])
    


used = [0]*N
que = [(w,c) for w,c in adj[0]]#コスト,番号
used[0] = 1
heapify(que)
ans = 0
while que:
    cv,v = heappop(que)#cvはコスト。vは番号
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w,c in adj[v]:#vを追加
        if used[c]:
            continue
        heappush(que,(w,c))
print(ans)


from heapq import *

def find(x):
    parent = data[x]
    if parent < 0: return x
    root = find(parent)
    data[x] = root
    return root

def union(x, y):
    root, second = find(x), find(y)
    if root == second: return False
    if height[root] < data[second]:
        second, root = root, second
    data[root] += data[second]
    height[root] = max(height[root], height[second]+1)
    data[second] = root
    return True

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N
E = [(0,0)] * N

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

X.sort()
Y.sort()
H = []

for i in range(N - 1):
    x1, j1 = X[i]
    x2, j2 = X[i + 1]
    y1, k1 = Y[i]
    y2, k2 = Y[i + 1]
    # ヒープ構造を用いて常にHの最初に最小値を持ってくる
    # X座標とY座標でそれぞれHに追加
    heappush(H, (x2 - x1, j1, j2))
    heappush(H, (y2 - y1, k1, k2))

answer = 0
data = [-1] * (N+1)  # 1-indexed rootには-sizeが入る
height = [0] * (N+1)

while H:
    w, s, t = heappop(H)
    # sとtの集合が異なっていた時、道を作る
    if union(s, t):
        answer += w

print(answer)


from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
from operator import itemgetter

n = int(input()) 
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

edge = set()

for key in [itemgetter(1),itemgetter(2)]:
    ixy.sort(key = key)
    for i in range(n-1):
        i1, i2 = ixy[i][0], ixy[i+1][0]
        x1, x2 = ixy[i][1], ixy[i+1][1]
        y1, y2 = ixy[i][2], ixy[i+1][2]
        d = min(abs(x2-x1), abs(y2-y1))
        edge.add((i1,i2,d))
    
row,col,value = zip(*edge)
csr_ = csr_matrix((value, (row,col)), shape=(n, n))
mst = minimum_spanning_tree(csr_, overwrite=True).astype(int)
print(mst.sum())

from heapq import *

def main():
    def find(x):
        parent = data[x]
        if parent < 0: return x
        root = find(parent)
        data[x] = root
        return root

    def union(x, y):
        root, second = find(x), find(y)
        if root == second: return False
        if height[root] < data[second]:
            second, root = root, second
        data[root] += data[second]
        height[root] = max(height[root], height[second]+1)
        data[second] = root
        return True

    N = int(input())
    X = [(0,0)] * N
    Y = [(0,0)] * N

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

    X.sort()
    Y.sort()
    H = []

    for i in range(N - 1):
        x1, j1 = X[i]
        x2, j2 = X[i + 1]
        y1, k1 = Y[i]
        y2, k2 = Y[i + 1]
        # ヒープ構造を用いて常にHの最初に最小値を持ってくる
        # X座標とY座標でそれぞれHに追加
        heappush(H, (x2 - x1, j1, j2))
        heappush(H, (y2 - y1, k1, k2))

    answer = 0
    data = [-1] * (N+1)  # 1-indexed rootには-sizeが入る
    height = [0] * (N+1)

    while H:
        w, s, t = heappop(H)
        # sとtの集合が異なっていた時、道を作る
        if union(s, t):
            answer += w

    print(answer)


def __starting_point():
    main()

__starting_point()

# built
# x軸の昇順で並べたリスト、y軸の昇順で並べたリストを作る。
# どちらかのリストで隣にある点同士を辺でむすぶ。
# 最小全域木

import sys
readline = sys.stdin.readline

N = int(readline())
point = [None] * N
for i in range(N):
  point[i] = list(map(int,readline().split())) + [i]
  
X = sorted(point, key = lambda x:x[0])
Y = sorted(point, key = lambda x:x[1])

G = [[] for i in range(N)]

for i in range(len(X) - 1):
  x1,y1,ind_1 = X[i]
  x2,y2,ind_2 = X[i + 1]
  G[ind_1].append([ind_2, min(abs(x1 - x2),abs(y1 - y2))])
  G[ind_2].append([ind_1, min(abs(x1 - x2),abs(y1 - y2))])
  
for i in range(len(Y) - 1):
  x1,y1,ind_1 = Y[i]
  x2,y2,ind_2 = Y[i + 1]
  G[ind_1].append([ind_2, min(abs(x1 - x2),abs(y1 - y2))])
  G[ind_2].append([ind_1, min(abs(x1 - x2),abs(y1 - y2))])

# 進むことができる頂点のうち、最もコストが小さいものを採用する
# heapqで、次に行くことができる(コスト, 頂点)を管理
# 頂点が追加されたら、そこから進むことができる頂点を全てheapqに追加する
# 訪問済み頂点はsetで管理することで除外
# 全てが訪問済みになったら（heapqが空になったら）終了

import heapq as hq
q = [(0, 0)]
hq.heapify(q)
visited = set()

ans = 0
while q:
  cost, v = hq.heappop(q)
  if v in visited:
    continue
  visited.add(v)
  ans += cost
  for child in G[v]:
    if child[0] in visited:
      continue
    hq.heappush(q, (child[1], child[0]))
  
print(ans)

class UnionFind():
    # 初めは全ての頂点が別々の木の根
    def __init__(self, n):  # n要素で初期化
        self.parent = list(range(n)) # 親
        self.rank = [0] * n   # 木の深さ

    def root_of(self, x):
        children = [x]
        while self.parent[x] != x:
            x = self.parent[x]
            children.append(x)

        for ch in children:
            self.parent[ch] = x
        return x

    # xとyの属する集合を併合
    def union(self, x, y):
        rx = self.root_of(x)
        ry = self.root_of(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]: # ランクの小さい木から大きい木の根に辺を張る
            self.parent[rx] = ry  # rxをryの子とする
        else:
            self.parent[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するかどうか
    def same(self, x, y):
        return self.root_of(x) == self.root_of(y)


N = int(input())
X = [None] * N
Y = [None] * N
for i in range(N):
    x, y = [int(x) for x in input().split()]
    X[i] = (x, i)
    Y[i] = (y, i)

X.sort()
Y.sort()
E = []
xp = X[0][0]
ip = X[0][1]
for (x, i) in X:
    E.append((x - xp, (ip, i)))
    xp = x
    ip = i

yp = Y[0][0]
ip = Y[0][1]
for (y, i) in Y:
    E.append((y - yp, (ip, i)))
    yp = y
    ip = i

E.sort()
uf = UnionFind(N)
cost = 0
for c, (e1, e2) in E:
    if uf.same(e1, e2): continue
    cost += c
    uf.union(e1, e2)

print(cost)

from heapq import *
N = int(input())
X,Y=[],[]
for n in range(N):
  x,y=map(int,input().split())
  X.append((x, n))
  Y.append((y, n))
X.sort()
Y.sort()
D=[[] for v in range(N)]
for n in range(N-1):
  cost = X[n+1][0]-X[n][0]
  D[X[n+1][1]].append((cost,X[n][1]))
  D[X[n][1]].append((cost,X[n+1][1]))
  cost=Y[n+1][0]-Y[n][0]
  D[Y[n+1][1]].append((cost,Y[n][1]))
  D[Y[n][1]].append((cost,Y[n+1][1]))

visited=[0]*N
pq = []
for w, t in D[0]:
  heappush(pq,(w,t))
visited[0]=1

ans = 0
while pq:
  w,t=heappop(pq)
  if visited[t]:
    continue
  visited[t]=1
  ans+=w
  for w,s in D[t]:
    if visited[s]==0:
      heappush(pq,(w,s))
print (ans)

n=int(input())
x=[]
y=[]
for i in range(n):
  xx,yy=map(int,input().split())
  x.append([xx,i])
  y.append([yy,i])
x.sort()
y.sort()
px=[]
py=[]
for i in range(n-1):
  px.append([x[i+1][0]-x[i][0],x[i][1],x[i+1][1]])
  py.append([y[i+1][0]-y[i][0],y[i][1],y[i+1][1]])
p=px+py
x=[]
y=[]
px=[]
py=[]
p.sort()
r=[i for i in range(n)]
rank=[1 for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(path):
  rx=root(path[1])
  ry=root(path[2])
  if rx==ry:
    return 0
  else:
    if rank[rx]>rank[ry]:
      r[rx]=ry
      rank[rx]+=rank[ry]
    else:
      r[ry]=rx
      rank[ry]+=rank[rx]
    return path[0]
ans=0
for i in range(len(p)):
  ans+=union(p[i])
print(ans)

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline

N=int(input())

xylist,yxlist=[],[]
par_dic={}
for i in range(N):
  x,y=map(int,input().split())
  xylist.append((x,y))
  yxlist.append((y,x))
  par_dic[(x,y)]=(x,y)
xylist.sort()
yxlist.sort()
#print(xylist)

elist=[]
for i in range(1,N):
  x1,y1=xylist[i-1]
  x2,y2=xylist[i]
  elist.append((min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
  y1,x1=yxlist[i-1]
  y2,x2=yxlist[i]
  elist.append((min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
#print(hq)
elist.sort(reverse=True)

def get_par(x):
  if x == par_dic[x]:
    return x
  else:
    par_dic[x] = get_par(par_dic[x])
    return par_dic[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_dic[par_y] = par_x
def is_same(x,y):
  return get_par(x) == get_par(y)

answer=0
while elist:
  d,p1,p2=elist.pop()
  #print(d,p1,p2)
  if not is_same(p1,p2):
    merge(p1,p2)
    answer+=d
  
print(answer)

import sys
from collections import defaultdict
finput=lambda:sys.stdin.readline().strip()

class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return 
        if self.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    coor=[list(map(int,finput().split()))+[i] for i in range(n)]
    coor.sort(key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew=dict(((coor[i][2],coor[i+1][2]),cost(coor[i][:2],coor[i+1][:2])) for i in range(n-1))
    coor.sort(key=lambda e:e[1])
    ew.update(dict(((coor[i][2],coor[i+1][2]),cost(coor[i][:2],coor[i+1][:2])) for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
def __starting_point():
    main()

__starting_point()

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

def kruskal(es, V):
    es.sort(key=lambda x:x[2])
    uf = UnionFind(V)
    res = 0
    for e in es:
        if not uf.same(e[0], e[1]):
            uf.union(e[0], e[1])
            res += e[2]
    return res

def resolve():
    N = I()
    xy = [LI() for _ in range(N)]

    # 辺の候補は、xyそれぞれでソートした隣同士の点の間のみに絞れる
    xy_x_asc = sorted(enumerate(xy), key=lambda x: x[1][0])
    xy_y_asc = sorted(enumerate(xy), key=lambda x: x[1][1])
    edge = []
    for i in range(N-1):
        xc = xy_x_asc[i][1][0]
        yc = xy_x_asc[i][1][1]
        xyc_num = xy_x_asc[i][0]
        xn = xy_x_asc[i+1][1][0]
        yn = xy_x_asc[i+1][1][1]
        xyn_num = xy_x_asc[i+1][0]
        edge.append([xyc_num, xyn_num, abs(xn-xc)])
    for i in range(N-1):
        xc = xy_y_asc[i][1][0]
        yc = xy_y_asc[i][1][1]
        xyc_num = xy_y_asc[i][0]
        xn = xy_y_asc[i+1][1][0]
        yn = xy_y_asc[i+1][1][1]
        xyn_num = xy_y_asc[i+1][0]
        edge.append([xyc_num, xyn_num, abs(yn-yc)])

    # print(edge)
    mst_cost = kruskal(edge, N)
    print(mst_cost)

def __starting_point():
    resolve()
__starting_point()

#Union Find
class union_find:
    #初期化
    #根なら-size,子なら親の頂点
    # par = [-1]*N
    def __init__(self, N):
        self.par = [-1]*N

    #xの根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合の併合
    def unite(self, x,y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if self.par[x] > self.par[y]:
                x,y = y,x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(self, x,y):
        return self.find(x) == self.find(y)

    #xが属する集合の個数
    def size(self, x):
        return -self.par[self.find(x)]

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

import heapq
edges = []
heapq.heapify(edges)

XYI.sort(key=lambda x: x[0])
for j in range(1, N):
    px, py, pi = XYI[j-1]
    x, y, i = XYI[j]
    d = min(abs(x-px), abs(y-py))
    heapq.heappush(edges, (d, pi, i))

XYI.sort(key=lambda x: x[1])
for j in range(1, N):
    px, py, pi = XYI[j-1]
    x, y, i = XYI[j]
    d = min(abs(x-px), abs(y-py))
    heapq.heappush(edges, (d, pi, i))

uf = union_find(N)
ans = 0
while True:
    d, i, j = heapq.heappop(edges)
    if uf.same(i, j): continue
    uf.unite(i, j)
    ans += d
    if uf.size(i) == N: break

print(ans)

class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return 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(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:
        i0,i1 = ds.find(i0), ds.find(i1)
        if i0 != i1:
            ds.union(i0,i1)
            yield d
print(sum(it()))

with open(0) as f:
    N, *xy = map(int, f.read().split())

from collections import namedtuple
v = namedtuple('v',['coordinate','num'])
#最小全域木に使われる辺は高々座標(xまたはy)が隣接する頂点間のものである
#したがって、x座標・y座標それぞれでソートして辺を求める
X = sorted([v(x,i) for x,i in zip(xy[::2], range(N))])
Y = sorted([v(y,i) for y,i in zip(xy[1::2], range(N))])

diffiter = lambda X:zip(X[:len(X)-1], X[1:]) #Xの1階階差差分のイテレータを返す関数
cost = lambda u,v:abs(u.coordinate - v.coordinate)
from itertools import chain
Edge = sorted([(cost(u,v), u.num, v.num) for u,v in chain(diffiter(X),diffiter(Y))])

root = namedtuple('root',['num', 'rank']) #(num_of_root, rank_of_root)
Root = [root(i,0) for i in range(N)]

def fr(i): #findRoot
    if i == Root[i].num:
        return Root[i]
    Root[i] = fr(Root[i].num)
    return Root[i]


def unionT(i, j): #unionTree
    p, q = fr(i), fr(j)
    if p.rank < q.rank:
        Root[p.num] = q
    elif p.rank > q.rank:
        Root[q.num] = p
    elif p.rank == q.rank:
        r, s = min(p, q), max(p, q)
        Root[r.num] = Root[s.num] = root(r.num, r.rank+1)
    

ans = 0
#最小全域木の大きさ算出(環状にならないように辺を小さい順に足してゆく)
for w, i, j in Edge:
    if fr(i).num == fr(j).num: #既に連結済み
        continue
    else:
        unionT(i,j)
        ans += w
print(ans)

n=int(input())
par=[-1]*n

# this par & rank are initialized lists
def find(x):
    nonlocal par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    nonlocal par
    if x==y:return False
    else:
        if par[x]>par[y]:x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True

def size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)

p=[]
edge=[]
for i in range(n):
  x,y=map(int,input().split())
  p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
  x0,_,j=p[i]
  x1,_,k=p[i+1]
  edge.append([x1-x0,j,k])

p.sort(key=lambda x:x[1])
for i in range(n-1):
  _,y0,j=p[i]
  _,y1,k=p[i+1]
  edge.append([y1-y0,j,k])

edge.sort()
ans=0
for i in range(len(edge)):
  cost,u,v=edge[i]
  if not same(u,v):
    unite(u,v)
    ans+=cost

print(ans)

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


class UnionFind:

    def __init__(self, n: int):
        self._n = n
        self._parents = [i for i in range(n)]
        self._rank = [1 for _ in range(n)]

    def unite(self, x: int, y: int) -> None:
        px = self.find(x)
        py = self.find(y)

        # 一致していないときはリンクをつける
        if px != py:
            self._link(px, py)

    def _link(self, x: int, y: int):
        if self._rank[x] < self._rank[y]:
            self._parents[x] = y
        elif self._rank[x] > self._rank[y]:
            self._parents[y] = x
        else:
            self._parents[x] = y
            self._rank[y] += 1

    def same(self, x: int, y: int) -> bool:
        px = self.find(x)
        py = self.find(y)
        return px == py

    def find(self, x: int) -> int:
        if self._parents[x] == x:
            return x

        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]


N = int(input())
ps = [list(map(int, input().split())) + [i] for i in range(N)]
ps.sort(key=lambda t: t[0])
xs = []
for i in range(N - 1):
    xs.append((ps[i + 1][0] - ps[i][0], ps[i][2], ps[i + 1][2]))

ps.sort(key=lambda t: t[1])
ys = []
for i in range(N - 1):
    ys.append((ps[i + 1][1] - ps[i][1], ps[i][2], ps[i + 1][2]))

xs += [(1<< 40, -1, -1)]
ys += [(1<< 40, -1, -1)]

xs.sort()
ys.sort()

xc, yc = 0, 0
uf = UnionFind(N)

ans = 0
while xc < N - 1 and yc < N - 1:
    if xs[xc][0] < ys[yc][0]:
        if not uf.same(xs[xc][1], xs[xc][2]):
            uf.unite(xs[xc][1], xs[xc][2])
            ans += xs[xc][0]
        xc += 1
    else:
        if not uf.same(ys[yc][1], ys[yc][2]):
            uf.unite(ys[yc][1], ys[yc][2])
            ans += ys[yc][0]
        yc += 1

print(ans)


def kruskal():
    '''
    最小全域木のコストを求める
    '''
    cost = 0
    edge.sort()

    for c, u, v in edge:
        if same(u, v):
            continue
        union(u, v)
        cost += c

    return cost


def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    '''
    xとyの属する集合を併合する
    '''
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x

    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


n = int(input())
x, y = [], []
for i in range(n):
    tmp_x, tmp_y = map(int, input().split())
    x.append([tmp_x, i])
    y.append([tmp_y, i])

x.sort()
y.sort()
edge = []
for i in range(n-1):
    edge.append([x[i+1][0]-x[i][0], x[i+1][1], x[i][1]])
    edge.append([y[i+1][0]-y[i][0], y[i+1][1], y[i][1]])

par = [-1] * n
print(kruskal())

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

Gx=sorted(G,key=lambda x:x[0])
Gy=sorted(G,key=lambda x:x[1])

newG=[]
for i in range(N-1):
    now=Gx[i]
    next=Gx[i+1]
    dist=abs(now[0]-next[0])
    newG.append((dist,now[2],next[2]))

for i in range(N-1):
    now=Gy[i]
    next=Gy[i+1]
    dist=abs(now[1]-next[1])
    newG.append((dist,now[2],next[2]))

newG.sort()

uf=UnionFind(N)
count=N
ans=0
for c,i,j in newG:
    if count==0:
        break

    if not uf.same(i,j):
        ans+=c
        uf.union(i,j)
        count-=1

print(ans)







N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, y, i))
    Y.append((y, x, i))
X.sort()
Y.sort()
Edges = list([] for _ in range(N))
for k in range(N-1):
    xk, yk, ik = X[k]
    xk_, yk_, ik_ = X[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    yk, xk, ik = Y[k]
    yk_, xk_, ik_ = Y[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    
import heapq
def prim(Edges, V):
    mst = []
    included = [False]*V
    heap = []
    included[0] = True
    for v, d in Edges[0]:
        heapq.heappush(heap, (d, 0, v)) #(dist, pre_v, cur_v)
    while heap:
        d, pre_v, cur_v = heapq.heappop(heap)
        if included[cur_v]:
            continue
        included[cur_v] = True
        mst.append((pre_v, cur_v, d))
        for next_v, dist in Edges[cur_v]:
            if not included[next_v]:
                heapq.heappush(heap, (dist, cur_v, next_v))
    return mst

mst = prim(Edges, N)
ans = 0
for v1, v2, d in mst:
    ans += d
    
print(ans)

from collections import defaultdict
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree


class Point:
 
    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    # Caclulate costs
    costs = defaultdict(int)
    costs_defined = defaultdict(int)
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        costs[(min_index, max_index)] = cost
        costs_defined[(min_index, max_index)] = 1
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        current_cost = costs[(min_index, max_index)]
        if costs_defined[(min_index, max_index)]:
            new_cost = min([cost, current_cost])
            costs[(min_index, max_index)] = new_cost
        else:
            costs[(min_index, max_index)] = cost
    # Create csgraph
    rows = list()
    cols = list()
    data = list()
    for node_pair, cost in costs.items():
        rows.append(node_pair[0])
        cols.append(node_pair[1])
        data.append(cost)
    return csr_matrix((data, (rows, cols)), shape=(N, N))

 
def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    graph = create_graph(N, points)
    mst = minimum_spanning_tree(graph)
    print(int(mst.sum()))
 
 
def __starting_point():
    main()
__starting_point()

import sys
input = sys.stdin.readline
N = int(input())
XY = [tuple(map(int,input().split() + [i])) for i in range(N)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)
sx = sorted(XY, key=lambda x:x[0])
sy = sorted(XY, key=lambda x:x[1])

es = []
for (x1,_,i),(x2,_,j) in zip(sx,sx[1:]):
    es.append((x2-x1, i, j))
for (_,y1,i),(_,y2,j) in zip(sy,sy[1:]):
    es.append((y2-y1, i, j))
es.sort(key=lambda x:x[0])

ans = 0
for d,i,j in es:
    if uf.is_same(i,j): continue
    uf.unite(i,j)
    ans += d
print(ans)

# D - Built?
import sys
import heapq

# input
N = int(input())

X, Y = [], []
for n in range(N):
    x, y = list(map(int, sys.stdin.readline().strip().split()))
    X.append((x, n))
    Y.append((y, n))

# build matrix
G = [[] for _ in range(N)]

X.sort()
Y.sort()
for i in range(N - 1):
    d_u, u = X[i]
    d_v, v = X[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))

    d_u, u = Y[i]
    d_v, v = Y[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))


# 最小全域木
q = []
fp = [False] * N  # 探索済み
fp[0] = True

for d, u in G[0]:
    heapq.heappush(q, (d, u))

ans = 0
while q:
    d, u = heapq.heappop(q)

    if fp[u]:
        continue
    fp[u] = True
    ans += d

    for d_v, v in G[u]:
        if fp[v]:
            continue
        heapq.heappush(q, (d_v, v))

print(ans)


import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush,heapify

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    x=[0]*n
    y=[0]*n
    for i in range(n):
#        xy[i]=list(map(int,input().split()))
        x[i],y[i]=list(map(int,input().split()))
elif icase==1:    
    n=3
#    xy=[[1, 5], [3, 9], [7, 8]]
    x=[1, 3, 7]
    y=[5, 9, 8]
elif icase==2:    
    n=6
#    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]
    x=[8, 4, 12,18,13,7]
    y=[3, 9, 19, 1, 5, 6]

xi=[[0]*2 for i in range(n)]
yi=[[0]*2 for i in range(n)]
for i in range(n):
    xi[i]=[x[i],i]
    yi[i]=[y[i],i]
    
xi.sort()
x=xi
y=yi.sort()
y=yi

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    wi=x[i+1][0]-x[i][0]
    heappush(que,(wi,x[i][1],x[i+1][1]))
    wi=y[i+1][0]-y[i][0]
    heappush(que,(wi,y[i][1],y[i+1][1]))

def find(x):
    if x == pair_lst[x]:
        return x
    else:
        tmp = find(pair_lst[x])
        pair_lst[x] = tmp
        return tmp

icnt=0
length_sum = 0
while que:
    w, s, t = heappop(que)
#    print(w,s,t)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w
        icnt+=1
#        print(icnt)

print(length_sum)   


# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
n = int(input())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

p = [] #点p
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k]) # 重みx_1 - x_0の点jと点kを繋ぐ辺
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])

edge.sort() #クラスカル法を使うので重みでソート
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)

N = int(input())
# XY_L = [[int(_) for _ in input().split()] for __ in range(N)]
X_L = [None] * N
Y_L = [None] * N
for i in range(N):
    _x, _y = list(map(int, input().split()))
    X_L[i] = [_x, i]
    Y_L[i] = [_y, i]

class UnionFind():
    def __init__(self, n):
        self.rank = [1] * n
        self.par = [int(_) for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)



X_L.sort()
Y_L.sort()
dx_l = [None] * (N-1)
dy_l = [None] * (N-1)
for i in range(N-1):
    dx_l[i] = [X_L[i+1][0] - X_L[i][0], X_L[i][1], X_L[i+1][1]]
    dy_l[i] = [Y_L[i+1][0] - Y_L[i][0], Y_L[i][1], Y_L[i+1][1]]

tmp_l = dx_l+dy_l
tmp_l.sort()

UF = UnionFind(N)
ans = 0

for _ in range(2*N-2):
    _d, _i, _j = tmp_l[_]
    if _i >= N or _j >= N:
        print((_i, _j))
    if UF.same(_i, _j):
        continue
    UF.unite(_i, _j)
    ans += _d

print(ans)



n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
x,y=zip(*xy)
x=list(zip(range(n),x))
y=list(zip(range(n),y))
x.sort(key=lambda a:a[1])
y.sort(key=lambda a:a[1])
d=[]
for i in range(n-1):
  d.append([x[i+1][1]-x[i][1],x[i+1][0],x[i][0]])
  d.append([y[i+1][1]-y[i][1],y[i+1][0],y[i][0]])
d.sort(key=lambda a:a[0],reverse=True)
# Union FInd
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

ans=0
uf=UnionFind(n)
while d:
  dist,i,j=d.pop()
  if uf.same(i,j):
    continue
  uf.union(i,j)
  ans+=dist
print(ans)

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)

N = int(input())
# XY_L = [[int(_) for _ in input().split()] for __ in range(N)]
X_L = [None] * N
Y_L = [None] * N
for i in range(N):
    _x, _y = list(map(int, input().split()))
    X_L[i] = [_x, i]
    Y_L[i] = [_y, i]

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# class UnionFind():
#     def __init__(self, n):
#         self.rank = [1] * n
#         self.par = [int(_) for _ in range(n)]

#     def find(self, x):
#         if self.par[x] == x:
#             return x
#         else:
#             self.par[x] == self.find(self.par[x])
#             return self.par[x]

#     def unite(self, x, y):
#         p_x = self.find(x)
#         p_y = self.find(y)
#         if p_x == p_y:
#             return False
#         if self.rank[p_x] < self.rank[p_y]:
#             self.par[p_x] = p_y
#         else:
#             self.par[p_y] = p_x
#             if self.rank[p_x] == self.rank[p_y]:
#                 self.rank[p_x] += 1
#         return True
    
#     def same(self, x, y):
#         if self.find(x) == self.find(y):
#             return True
#         else:
#             return False

X_L.sort()
Y_L.sort()
dx_l = [None] * (N-1)
dy_l = [None] * (N-1)
for i in range(N-1):
    dx_l[i] = [X_L[i+1][0] - X_L[i][0], X_L[i][1], X_L[i+1][1]]
    dy_l[i] = [Y_L[i+1][0] - Y_L[i][0], Y_L[i][1], Y_L[i+1][1]]

tmp_l = dx_l+dy_l
tmp_l.sort()

UF = UnionFind(N)
ans = 0

for _ in range(2*N-2):
    _d, _i, _j = tmp_l[_]
    if UF.same(_i, _j):
        continue
    UF.unite(_i, _j)
    ans += _d
    # if _ % 1000 == 0:
    #     print(_,ans)



print(ans)



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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
x, y = [], []
for i in range(N):
    a, b = list(map(int, input().split()))
    x.append([a, i])
    y.append([b, i])
x.sort()
y.sort()

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

uft = UnionFind(N)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.union(s, t)
        ans += w

print(ans)


n=int(input())
x=[]
y=[]
for i in range(n):
  xx,yy=map(int,input().split())
  x.append([xx,i])
  y.append([yy,i])
x.sort()
y.sort()
px=[[x1-x0,i0,i1] for (x0,i0),(x1,i1) in zip(x,x[1:])]
py=[[y1-y0,i0,i1] for (y0,i0),(y1,i1) in zip(y,y[1:])]
p=px+py
x=[]
y=[]
px=[]
py=[]
p.sort()
r=[i for i in range(n)]
rank=[1 for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(path):
  rx=root(path[1])
  ry=root(path[2])
  if rx==ry:
    return 0
  else:
    if rank[rx]>rank[ry]:
      r[rx]=ry
      rank[rx]+=rank[ry]
    else:
      r[ry]=rx
      rank[ry]+=rank[rx]
    return path[0]
ans=0
for i in range(len(p)):
  ans+=union(p[i])
print(ans)

class UnionFind:
    def __init__(self, n):
        self.v = [-1] * n

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.v[self.find(x)]


def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    N = int(input())

    ps = []
    xs = set()
    ys = set()
    for i in range(N):
        x, y = list(map(int, input().split()))
        ps.append((x, y))
        xs.add(x)
        ys.add(y)

    xs = tuple(sorted(xs))
    ys = tuple(sorted(ys))

    dx = {e: i for i, e in enumerate(xs)}
    dy = {e: i for i, e in enumerate(ys)}

    uf = UnionFind(N * 2)
    for x, y in ps:
        uf.unite(dx[x], dy[y] + N)

    def make_edges(xs, d, *, add_val=0):
        xes = []
        for x0, x1 in zip(xs, xs[1:]):
            xes.append((abs(x1 - x0), d[x0] + add_val, d[x1] + add_val))
        return xes

    xes = make_edges(xs, dx)
    yes = make_edges(ys, dy, add_val=N)

    # Kruskal
    # 最小コストの辺から順に使用する
    # 同じ連結成分に属していればつながない(閉路を作らない)
    # コスト昇順ソート済みの辺リストを使用する
    ret = 0
    joined = set()
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        if (a in joined) or (b in joined): continue
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**5)

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:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            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(input())
X, Y = [], []
for i in range(N):
    x, y = 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)

import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = set()
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    
row,col,value = list(zip(*edge))
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))

from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)


import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

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

    def find(self, x):
        """
        親が同じか判別する
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        yをxの根に繋ぐ
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n = int(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()
    edge = []
    for i in range(1, n):
        cost1 = X[i][0] - X[i - 1][0]
        edge.append([cost1, X[i - 1][1], X[i][1]])
        cost2 = Y[i][0] - Y[i - 1][0]
        edge.append([cost2, Y[i - 1][1], Y[i][1]])

    uf = UnionFind(n)
    res = uf.kruskal(edge)
    print(res)


def __starting_point():
    resolve()

__starting_point()

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n = int(input())
graphx = []
graphy = []

for i in range(n):
    x,y = map(int,input().split())
    graphx.append((x,y,i))
    graphy.append((x,y,i))
graphx = sorted(graphx, key=lambda x:x[0])
graphy = sorted(graphy, key=lambda x:x[1])
graph = []


for k in range(n-1):
    i,j = graphx[k][2], graphx[k+1][2]
    x0,x1 = graphx[k][0],graphx[k+1][0]
    m = abs(x0-x1)
    graph.append((m,i,j))

for k in range(n-1):
    i,j = graphy[k][2], graphy[k+1][2]
    y0,y1 = graphy[k][1],graphy[k+1][1]
    m = abs(y0-y1)
    graph.append((m,i,j))


graph.sort()
#print(graph)

ans = 0
uf = UnionFind(n)
for c,i,j in graph:
    if not uf.same(i,j):
        ans += c
        uf.union(i,j)
print(ans)

def main():
	import sys
	input=sys.stdin.readline
	n=int(input())
	xy=[]
	node=[[]for _ in range(n)]
	for i in range(n):
		x,y=map(int,input().split())
		xy.append((i,x,y))
	xy.sort(key=lambda x:x[1])
	for i in range(len(xy)-1):
		node[xy[i][0]].append((abs(xy[i][1]-xy[i+1][1]),xy[i+1][0]))#dis,num
		node[xy[i+1][0]].append((abs(xy[i][1]-xy[i+1][1]),xy[i][0]))#dis,num
	xy.sort(key=lambda x:x[2])
	for i in range(len(xy)-1):
		node[xy[i][0]].append((abs(xy[i][2]-xy[i+1][2]),xy[i+1][0]))#dis,num
		node[xy[i+1][0]].append((abs(xy[i][2]-xy[i+1][2]),xy[i][0]))#dis,num
	from heapq import heappop,heappush
	visited=[False]*n
	visited[0]=True
	pq=[]
	for x in node[0]:
		heappush(pq,(x[0],x[1]))
	ans=0
	for _ in range(n-1):
		while True:
			u=heappop(pq)
			if visited[u[1]]==False:
				break
		ans+=u[0]
		pre_dis=u[0]
		u_dis=u[0];u_num=u[1]
		ans+=abs(u_dis-pre_dis)
		visited[u_num]=True
		for x in node[u_num]:
			x_dis=x[0];x_num=x[1]
			if visited[x_num]==False:
				heappush(pq,(x_dis,x_num))
	print(ans)
def __starting_point():
	main()
__starting_point()

import sys
sys.setrecursionlimit(10**5)
n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append((i, x, y))
xx = sorted(xy, key=lambda x:x[1])
yy = sorted(xy, key=lambda x:x[2])
li = []
for i in range(n-1):
    li.append((xx[i][0], xx[i+1][0], xx[i+1][1]-xx[i][1]))
    li.append((yy[i][0], yy[i+1][0], yy[i+1][2]-yy[i][2]))
li.sort(key=lambda x:x[2])
class UnionFind():
    def __init__(self, li):
        self.li = li
    def root(self, x):
        if self.li[x]==x:
            return x
        self.li[x] = self.root(self.li[x])
        return self.li[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return
        self.li[ry] = rx
    def same(self, x, y):
        return self.root(x)==self.root(y)
uf = UnionFind(list(range(n)))
ans = 0
for x, y, cost in li:
    if uf.same(x, y):
        continue
    uf.unite(x, y)
    ans += cost
print(ans)

class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

    def ifSame(self, x, y):
        return self.root(x) == self.root(y)

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])

# edge=[cost, place, place] sorted by cost.
# place are expected to be 0 to N-1
# N : vertical count


def clascal(N, E, tree_count=1):
    #E[weight, vertical, vertical]
    tree = UnionFind(N)
    weight = 0
    counter = 0
    # E[w, A, B]
    for e in sorted(E):
        if counter >= N-1:
            break
        if tree.ifSame(e[1], e[2]):
            continue
        else:
            tree.unite(e[1], e[2])
            weight += e[0]
            counter += 1
    return weight


# いつもここから
N = int(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()
diff = []
for i in range(N - 1):
    diff.append((X[i + 1][0] - X[i][0], X[i][1], X[i+1][1]))
    diff.append((Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]))
diff.sort()
print((clascal(N, diff)))


import sys
sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

n=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(n)]
G=[]

# MSTを求める
xy.sort()
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  G.append((min(abs(sx-tx),abs(sy-ty)),si,ti))

xy.sort(key=lambda x:x[1])
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  G.append((min(abs(sx-tx),abs(sy-ty)),si,ti))

# Kruskal 法
u=UnionFind(n)
ans=0
G.sort()
for c,x,y in G:
  if u.root_same(x,y):continue
  u.unite(x,y)
  ans+=c
print(ans)


N = int(input())
Xs = []
Ys = []
for i in range(N):
    x, y = map(int, input().split())
    Xs.append((x, i))
    Ys.append((y, i))
Xs.sort()
Ys.sort()
Edges = []
for i in range(1, N):
    (x1, v1), (x2, v2) = Xs[i-1], Xs[i]
    Edges.append((abs(x1-x2), v1, v2))
    (y1, v1), (y2, v2) = Ys[i-1], Ys[i]
    Edges.append((abs(y1-y2), v1, v2))

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

import heapq
heapq.heapify(Edges)
uf = UnionFind(N)
ans = 0
while Edges:
    d, a, b = heapq.heappop(Edges)
    if not uf.same(a, b):
        ans += d
        uf.union(a, b)
print(ans)

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
n=int(input())
points=[list(map(int,input().split()))+[i] for i in range(n)]
points.sort(key = lambda x:x[1])
edge=[]
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][1]-points[i][1]))
points.sort()
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][0]-points[i][0]))
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
    
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    
    def getsize(self, x):
        return self.size[self.root(x)]
edge.sort(key=lambda x:x[2])
uf=UnionFind(n)
ans=0
for ed in edge:
    if uf.issame(ed[0],ed[1]):continue
    ans+=ed[2]
    uf.merge(ed[0],ed[1])
print(ans)

from heapq import heappop,heappush
import sys
sys.setrecursionlimit(10**6)
n=int(input())
pair=[i for i in range(n)]
que=[]
e=[None]*n
for i in range(n):
  x,y=map(int,input().split())
  e[i]=(i,x,y)
ex=sorted(e,key=lambda x:x[1])
ey=sorted(e,key=lambda x:x[2])
for i in range(n-1):
  w=ex[i+1][1]-ex[i][1]
  heappush(que,(w,ex[i][0],ex[i+1][0]))
for i in range(n-1):
  w=ey[i+1][2]-ey[i][2]
  heappush(que,(w,ey[i][0],ey[i+1][0]))
def find(x):
  if x==pair[x]:return x
  else:
    tmp=find(pair[x])
    pair[x]=tmp
    return tmp
q=[]
ans=0
while que:
  w,s,t=heappop(que)
  root_s=find(s)
  root_t=find(t)
  if root_s!=root_t:
    pair[root_s]=root_t
    ans+=w
print(ans)

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

from itertools import permutations
n = int(input())
list_XY = []
list_CO = []
for i in range(n):
    x, y = map(int, input().split())
    list_XY.append([x, y, i])

list_XY.sort(key=lambda x:x[0])
for i in range(n-1):
    list_CO.append([list_XY[i][2], list_XY[i+1][2], abs(list_XY[i][0]-list_XY[i+1][0])])

list_XY.sort(key=lambda x:x[1])
for i in range(n-1):
    list_CO.append([list_XY[i][2], list_XY[i+1][2], abs(list_XY[i][1]-list_XY[i+1][1])])

list_CO.sort(key=lambda x:x[2])
uf = UnionFind(n)
ans = 0

for i, j, cost in list_CO:
    if not uf.same(i, j):
        uf.union(i, j)
        ans += cost
    if uf.size(0) == n:
        break

print(ans)

class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    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):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

X.sort()
Y.sort()
road = []

def add_cand(Z):
  nonlocal road
  z1, i1 = Z[0]
  for j in range(1, N):
    z2, i2 = Z[j]
    road.append((z2-z1, i1, i2))
    z1, i1 = z2, i2

add_cand(X); add_cand(Y)

road.sort()
ans = 0
for cost, i, j in road:
  if uf.is_same(i, j):
    continue
  uf.union(i, j)
  ans += cost

print(ans)

class DisjointSets:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.siz = [1]*n

    def root(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def same(self,x,y): 
        return self.root(x) == self.root(y)

    def unite(self,x,y): 
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.siz[x] < self.siz[y]:
            x,y = y,x
        self.parent[y] = x
        self.siz[x] += self.siz[y]

    def size(self,x):
        return self.siz[self.root(x)]
        
n = int(input())
X = []
Y = []
for i in range(n):
    x,y = list(map(int,input().split()))
    X.append((i,x))
    Y.append((i,y))
X.sort(key = lambda x:x[1])
Y.sort(key = lambda y:y[1])
edges = []
for i in range(1,n):
    a,x1 = X[i-1]
    b,x2 = X[i]
    edges.append((a,b,x2-x1))
    c,y1 = Y[i-1]
    d,y2 = Y[i]
    edges.append((c,d,y2-y1))
edges.sort(key = lambda y:y[2])

ans = 0
ds = DisjointSets(n)
for i in range(2*n-2):
    u,v,dist = edges[i]
    if ds.same(u,v): continue
    ds.unite(u,v)
    ans += dist
print(ans)


import heapq


class UnionFind:
    from collections import deque

    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = self.deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


N = int(input())
V = []
for i in range(N):
    s, t = list(map(int, input().split(' ')))
    V.append((i, s, t))

E = []
vx = sorted(V, key=lambda v: v[1])
for v1, v2 in zip(vx, vx[1:]):
    i, x1, y1 = v1
    j, x2, y2 = v2
    heapq.heappush(E, (abs(x1 - x2), i, j))

vy = sorted(V, key=lambda v: v[2])
for v1, v2 in zip(vy, vy[1:]):
    i, x1, y1 = v1
    j, x2, y2 = v2
    heapq.heappush(E, (abs(y1 - y2), i, j))

uf = UnionFind(N)
cost = 0
while E:
    c, i, j = heapq.heappop(E)
    if not uf.find(i, j):
        uf.union(i, j)
        cost += c

print(cost)


from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

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

length, frm, to = [], [], []
path_set = set()


def path(axis):
    A.sort(key=lambda x: x[axis])
    for i in range(N - 1):
        if (A[i][0], A[i + 1][0]) in path_set:
            continue
        length.append(min(abs(A[i][1] - A[i + 1][1]),
                          abs(A[i][2] - A[i + 1][2])))
        frm.append(A[i][0])
        to.append(A[i + 1][0])
        path_set.add((A[i][0], A[i + 1][0]))


path(1)
path(2)
matr = csr_matrix((length, (frm, to)), shape=(N, N))

T = minimum_spanning_tree(matr).astype(int)
print((sum(T.data)))



# n個の要素を0~N-1で管理
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    # グループの数を返す
    def group_count(self):
        return len(self.roots())

    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def resolve():
    N = int(input())
    X = []
    Y = []
    # 町のナンバーも付ける
    for i in range(N):
        x, y = map(int, input().split())
        X.append((i, x))
        Y.append((i, y))

    # 短い距離にある街をつなげば良いのでソートする
    X.sort(key=lambda x: x[1])
    Y.sort(key=lambda x: x[1])

    # コストを計算しグラフを作成
    G = []
    for i in range(1, N):
        a, x1 = X[i - 1]
        b, x2 = X[i]
        G.append((a,b,x2-x1))
        a, y1 = Y[i - 1]
        b, y2 = Y[i]
        G.append((a, b, y2 - y1))

    # クラシカル法で最小全域木
    ans = 0
    uf = UnionFind(N)
    G.sort(key=lambda x: x[2])
    for a, b, w in G:
        if not uf.is_same(a, b):
            uf.union(a, b)
            ans += w
    print(ans)

def __starting_point():
    resolve()
__starting_point()

import sys
input = sys.stdin.readline
N = int(input())
XYI = [tuple(map(int,input().split() + [i])) for i in range(N)]
sx = sorted(XYI, key=lambda x:x[0])
sy = sorted(XYI, key=lambda x:x[1])

es = []
for (x0,_,i0),(x1,_,i1) in zip(sx,sx[1:]):
    es.append((x1-x0, i0, i1))
for (_,y0,i0),(_,y1,i1) in zip(sy,sy[1:]):
    es.append((y1-y0, i0, i1))
es.sort(key=lambda x:x[0])

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]
uf = UnionFind(N)

ans = 0
for d,a,b in es:
    if uf.is_same(a,b): continue
    uf.unite(a,b)
    ans += d
print(ans)

import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
from operator import itemgetter

N = int(input())
P = []
for i in range(N):
  x,y = map(int, input().split())
  P.append((x,y,i))
  
data = [10, 20, 30, 40]
row = [0, 0, 1, 1]
col = [1, 2, 0, 2]

#print(csr_matrix((data, (row, col))).toarray())
  
data = []
row = []
col = []

P.sort() 
D = {}
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

P.sort(key=itemgetter(1))
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  if (p,q) in D:
    continue
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

coo = coo_matrix((data, (row, col)), (N, N))
mst = minimum_spanning_tree(coo)
print(int(mst.sum()))

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


# Union Find（経路圧縮有）
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 親が同じか判別
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 根を繋ぎ直す
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 親が同じか判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 連結成分の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


def kruskal(max_node, edge):
    """
    :param max_node: UnionFind木に渡す頂点数です
    :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
    :return: 最小全域木のコストの和
    """
    edge.sort()
    uf = UnionFind(max_node)
    cost_sum = 0
    for cost, node1, node2 in edge:
        if not uf.same(node1, node2):
            cost_sum += cost
            uf.union(node1, node2)
    return cost_sum


def resolve():
    n = int(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()
    cost = []
    for i in range(n - 1):
        cost.append([abs(X[i][0] - X[i + 1][0]), X[i][1], X[i + 1][1]])
        cost.append([abs(Y[i][0] - Y[i + 1][0]), Y[i][1], Y[i + 1][1]])

    res = kruskal(n, cost)
    print(res)


def __starting_point():
    resolve()

__starting_point()

from scipy.sparse import *
from scipy.sparse.csgraph import *
N = int(input())
T = [[n]+list(map(int,input().split())) for n in range(N)]
P = set()

for i in [1,2]:
  T.sort(key=lambda a: a[i])
  for j in range(1,N):
    i0,x0,y0 =  T[j-1]
    i1,x1,y1 =  T[j]
    P.add((min(abs(x1-x0),abs(y1-y0)),i0,i1))

d,i,j = zip(*P)
G = csr_matrix((d,(i,j)),shape=(N,N))
print(int(minimum_spanning_tree(G).sum()))

import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

n=int(input())
xy=[list(map(int,input().split()))+[i]for i in range(n)]
xy.sort()
edge=[]
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  edge.append((min(abs(sx-tx),abs(sy-ty)),si,ti))
xy.sort(key=lambda x:x[1])
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  edge.append((min(abs(sx-tx),abs(sy-ty)),si,ti))
u=UnionFind(n)
ans=0
edge.sort()
for c,x,y in edge:
  if u.root_same(x,y):continue
  u.unite(x,y)
  ans+=c
print(ans)

# atcoder problem solving

# Built?
import sys
input=sys.stdin.readline
N = int(input())
d = []

for i in range(N):
    x, y = list(map(int, input().split()))
    d.append((i+1, x, y))

edge = []

# x座標に関する辺の設定

d.sort(key=lambda x: x[1])

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(px-qx)

    edge.append((dis, a, b))
    edge.append((dis, b, a))

# y座標に関する辺の設定

d.sort(key=lambda x: x[2])

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(py-qy)

    edge.append((dis, a, b))
    edge.append((dis, b, a))


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

edge.sort()
# 最小全域木（クラスかるほう）
def kruskal():
    res = 0
    G = UnionFind(N)
    for cost, p, q, in edge:
        if not G.same(p, q):
            G.union(p, q)
            res += cost
    return res


ans = kruskal()

print(ans)


class UnionFind:
    def __init__(self, n):
        self.v = [-1] * n

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.v[self.find(x)]


def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    N = int(input())

    ps = []
    xs = set()
    ys = set()
    for i in range(N):
        x, y = list(map(int, input().split()))
        ps.append((x, y))
        xs.add(x)
        ys.add(y)

    xs = tuple(sorted(xs))
    ys = tuple(sorted(ys))

    dx = {e: i for i, e in enumerate(xs)}
    dy = {e: i for i, e in enumerate(ys)}

    uf = UnionFind(N * 2)
    for x, y in ps:
        uf.unite(dx[x], dy[y] + N)

    def make_edges(xs, d, *, add_val=0):
        xes = []
        for x0, x1 in zip(xs, xs[1:]):
            xes.append((abs(x1 - x0), d[x0] + add_val, d[x1] + add_val))
        return xes

    xes = make_edges(xs, dx)
    yes = make_edges(ys, dy, add_val=N)

    # Kruskal
    # 最小コストの辺から順に使用する
    # 同じ連結成分に属していればつながない(閉路を作らない)
    # コスト昇順ソート済みの辺リストを使用する
    ret = 0
    # joined = set()
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        # if (a in joined) or (b in joined): continue
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


def __starting_point():
    main()

__starting_point()

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

import copy
N = int(input())
A = [0] * N
for i in range(N):
  a, b = list(map(int, input().split()))
  A[i] = [i, a, b]

B = copy.deepcopy(A)  
A = sorted(A, key = lambda x:x[1])
B = sorted(B, key = lambda x:x[2])
#print(A, B)

#それぞれの辺のながさを求めて、小さい順にする
#[点の番号、点の番号、２点間距離]
A2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(A[i][1] - A[i - 1][1])
  A2[i - 1] = [A[i][0], A[i - 1][0], l]

B2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(B[i][2] - B[i - 1][2])
  B2[i - 1] = [B[i][0], B[i - 1][0], l]  
Len = A2 + B2
Len = sorted(Len, key = lambda x:x[2])
#print(Len)

data = UnionFind(N + 1)
cost = 0
for i in range(len(Len)):
    if not data.same_check(Len[i][0], Len[i][1]):
      data.union(Len[i][0], Len[i][1])
      cost += Len[i][2]

  
print(cost)  
  
  



from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = set()
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    
# csr形式に直す
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

class UnionFind:
    def __init__(self,n):
        self.v=[-1]*n
    
    def find(self,x):
        if self.v[x]<0:
            return x
        else:
            self.v[x]=self.find(self.v[x])
            return self.v[x]
    
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return False
        else:
            if self.v[x]>self.v[y]:
                x,y=y,x
            self.v[x]+=self.v[y]
            self.v[y]=x
            return True
    
    def same(self,x,y):
        return self.find(x)==self.find(y)
    
    def size(self,x):
        return -self.v[self.find(x)]

import sys

N=int(sys.stdin.readline())
ps=[]
xs=set()
ys=set()
for i in range(N):
    x,y=map(int,input().split())
    ps.append((x,y))
    xs.add(x)
    ys.add(y)

xs=tuple(sorted(xs))
ys=tuple(sorted(ys))

dx={e:i for i,e in enumerate(xs)}
dy={e:i for i,e in enumerate(ys)}
uf=(UnionFind(N*2))
for x,y in ps:
    uf.unite(dx[x],dy[y]+N)

def make_edges(xs,start):
    xes=[]
    for i, (x0,x1) in enumerate(zip(xs,xs[1:]),start=start):
        xes.append((abs(x1-x0), i, i+1))
    return xes

xes=make_edges(xs,start=0)
yes=make_edges(ys,start=N)

ret=0
for cost,a,b in sorted(xes+yes,key=lambda x:x[0]):
    if uf.same(a,b):
        continue
    uf.unite(a,b)
    ret+=cost
print(ret)

import heapq
def prim():
    used = [True]*n
    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(input())
P = []
for i in range(n):
    x, y = map(int, input().split())
    P.append((x, y, i))
P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))
P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))
print(prim())

#UnionFind木とそれを利用したクラスカル法
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
                x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def nums(self,x):
        return abs(self.parents[self.find(x)])

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
edge = []
A.sort()
for i in range(N-1):
    w = A[i+1][0]-A[i][0]
    edge.append((w,A[i][2],A[i+1][2]))
A.sort(key=lambda x:x[1])
for i in range(N-1):
    w = A[i+1][1]-A[i][1]
    edge.append((w,A[i][2],A[i+1][2]))

edge.sort()

uf = UnionFind(N)
ans = 0
for i in range(len(edge)):
    u,x,y = edge[i]
    if not uf.same(x,y):
        uf.union(x,y)
        ans += u
print(ans)

from heapq import heapify, heappop, heappush
N, *A = list(map(int, open(0).read().split()))
*A, = list(zip(*[iter(A)]*2))
A = [(x, y, i) for i, (x, y) in enumerate(A)]
A.sort()
G = []
x0, y0, i0 = A[0]
for x, y, i in A[1:]:
    c = min(abs(x-x0), abs(y-y0))
    heappush(G, (c, i0, i))
    x0, y0, i0 = x, y, i
A.sort(key=lambda x: x[1])
x0, y0, i0 = A[0]
for x, y, i in A[1:]:
    c = min(abs(x-x0), abs(y-y0))
    heappush(G, (c, i0, i))
    x0, y0, i0 = x, y, i


class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

    def root(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


ans = 0
u = UnionFind(N)
while u.num_union() > 1:
    c, a, b = heappop(G)
    if u.same(a, b):
        continue
    u.unite(a, b)
    ans += c

print(ans)


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

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

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def size(self,x):
        return -self.parents[self.find(x)]

    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def members(self,x):
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x<0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n=int(input())
X=[]
Y=[]
for i in range(n):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])
X.sort()
Y.sort()
E=[]
for i in range(n-1):
    E.append([X[i+1][0]-X[i][0],X[i][1],X[i+1][1]])
    E.append([Y[i+1][0]-Y[i][0],Y[i][1],Y[i+1][1]])
E.sort()
U=UnionFind(n)
ans=0
for i in range(2*n-2):
    d=E[i][0]
    j1=E[i][1]
    j2=E[i][2]
    if not U.same(j1,j2):
        ans+=d
        U.union(j1,j2)
print(ans)

class Union():
    def __init__(self, n):
        self.para = [-1] * n
    
    def find(self, n):
        if self.para[n] < 0:
            return n
        
        else:
            self.para[n] = self.find(self.para[n])
            return self.para[n]
    
    def union(self, n, m):
        n = self.find(n)
        m = self.find(m)
        if n == m:
            return False
        else:
            if self.para[n] > self.para[m]:
                n, m = m, n
            
            self.para[n] += self.para[m]
            self.para[m] = n
    
    def same(self, n, m):
        return self.find(n) == self.find(m)

N = int(input()) 
X, Y = [], [] 
for i in range(N): 
    x,y = map(int,input().split()) 
    X.append((x,i)) 
    Y.append((y,i))
X.sort()
Y.sort()
ALL = []
for i in range(len(X)-1):
    ALL.append((X[i+1][0]-X[i][0], X[i][1], X[i+1][1]))
    ALL.append((Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]))
ALL.sort()
ut = Union(N)
cnt = 0
for a in ALL:
    n = a[1]
    m = a[2]
    if not ut.same(n,m):
        ut.union(n,m)
        cnt += a[0]
print(cnt)

import sys
sys.setrecursionlimit(10**7)


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n = int(input())
xy = [list(map(int, input().split()))+[i] for i in range(n)]
G = []

xy.sort()
for j in range(1, n):
    sx, sy, si = xy[j-1]
    tx, ty, ti = xy[j]
    G.append((min(abs(sx-tx), abs(sy-ty)), si, ti))

xy.sort(key=lambda x: x[1])
for j in range(1, n):
    sx, sy, si = xy[j-1]
    tx, ty, ti = xy[j]
    G.append((min(abs(sx-tx), abs(sy-ty)), si, ti))

uf = UnionFind(n)
ans = 0
G.sort()
for c, x, y in G:
    if uf.same(x, y):
        continue
    uf.union(x, y)
    ans += c
print(ans)


from operator import itemgetter


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False


def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort()
    res = 0
    for d, s, t in edges:
        if not uf.same(s, t):
            uf.unite(s, t)
            res += d
    return res

n = int(input())

xy = [[i] + list(map(int, input().split())) for i in range(n)] 

edges = set()
for key in [itemgetter(1), itemgetter(2)]:
    xy.sort(key = key)
    for i in range(n-1):
        i1, x1, y1 = xy[i]
        i2, x2, y2 = xy[i+1]
        d = min(abs(x1 - x2), abs(y1 - y2))
        edges.add((d, i1, i2))

edges = list(edges)
print((kruskal(n, edges)))


N = int(input())
XYI = [tuple(map(int,input().split() + [i])) for i in range(N)]
sx = sorted(XYI, key=lambda x:x[0])
sy = sorted(XYI, key=lambda x:x[1])

es = []
for (x0,_,i0),(x1,_,i1) in zip(sx,sx[1:]):
  es.append((x1-x0, i0, i1))
for (_,y0,i0),(_,y1,i1) in zip(sy,sy[1:]):
  es.append((y1-y0, i0, i1))
es.sort(key=lambda x:x[0])
 
class UnionFind:
  def __init__(self,N):
    self.parent = [i for i in range(N)]
    self._size = [1] * N
    self.count = 0
  def root(self,a):
    if self.parent[a] == a:
      return a
    else:
      self.parent[a] = self.root(self.parent[a])
      return self.parent[a]
  def is_same(self,a,b):
    return self.root(a) == self.root(b)
  def unite(self,a,b):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb: return
    if self._size[ra] < self._size[rb]: ra,rb = rb,ra
    self._size[ra] += self._size[rb]
    self.parent[rb] = ra
    self.count += 1
  def size(self,a):
    return self._size[self.root(a)]

uf = UnionFind(N)
ans = 0
for d,a,b in es:
  if uf.is_same(a,b): continue
  uf.unite(a,b)
  ans += d
print(ans)

N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y,i))
A=sorted(A)
B=sorted(A,reverse=False, key=lambda x: x[1]) 
#print(A,B)
E=[[]for i in range(N)]
for i in range(N-1):
  x1,x2=A[i][2],A[i+1][2]
  y1,y2=B[i][2],B[i+1][2]
  E[x1].append((x2,A[i+1][0]-A[i][0]))
  E[x2].append((x1,A[i+1][0]-A[i][0]))
  E[y1].append((y2,B[i+1][1]-B[i][1]))
  E[y2].append((y1,B[i+1][1]-B[i][1]))
G=E
# G[v] = [w, ...]
#     グラフG上で頂点vが隣接する辺集合

from heapq import heappush, heappop, heapify
used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)

ans=0
while que:
    cv,v=heappop(que)
    if used[v]:
        continue
    used[v]=1
    ans+=cv
    for w,c in G[v]:
        if used[w]:
            continue
        heappush(que,(c,w))
print(ans)

import heapq

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n = int(input())
xy = [list(map(int, input().split()))+[i] for i in range(n)]
"""
辺を結びたいがすべての点で結ぶと膨大になる
"""

edge = []
xy.sort()
for i, j in zip(list(range(n-1)), list(range(1, n))):
    cost = xy[j][0] - xy[i][0]
    heapq.heappush(edge, [cost, xy[i][2], xy[j][2]])

xy.sort(key= lambda x: x[1])
for i, j in zip(list(range(n-1)), list(range(1, n))):
    cost = xy[j][1] - xy[i][1]
    heapq.heappush(edge, [cost, xy[i][2], xy[j][2]])

uf = UnionFind(n)
ans = 0
while edge:
    c, a, b = heapq.heappop(edge)
    if uf.same(a, b): continue
    uf.union(a, b)
    ans += c

print(ans)


from copy import deepcopy as copy
from operator import itemgetter

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]#それぞれの要素の根を再帰的に求める

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def main():
    n = int(input())
    bridge = [None]*n
    for i in range(n):
        bridge[i] = [int(x) for x in input().split()]+[i]

    judge = []

    bridge.sort()
    for i in range(n-1):
        judge.append((bridge[i+1][0]-bridge[i][0], bridge[i][2], bridge[i+1][2]))

    bridge.sort(key=itemgetter(1))
    for i in range(n-1):
        judge.append((bridge[i+1][1]-bridge[i][1], bridge[i][2], bridge[i+1][2]))
    
    judge.sort()
    union = UnionFind(n)
    count = 0
    cost = 0
    for k in range(2*n):
        c, i, j = judge[k]
        if union.same(i, j):
            continue
        union.union(i, j)
        cost += c
        count += 1
        if count == n-1:
            break
    
    print(cost)

def __starting_point():
    main()
__starting_point()

import sys
import heapq
input = sys.stdin.readline


n = int(input())
Xs = []
Ys = []
for i in range(n):
    x, y = map(int, input().split())
    Xs.append((x-1, i))
    Ys.append((y-1, i))

Xs.sort()
Ys.sort()

edges = [[] for _ in range(n)]
for i in range(n-1):
    x, node = Xs[i]
    nx, new_node = Xs[i+1]
    edges[node].append((nx-x, new_node))
    edges[new_node].append((nx-x, node))

for i in range(n-1):
    y, node = Ys[i]
    ny, new_node = Ys[i+1]
    edges[node].append((ny-y, new_node))
    edges[new_node].append((ny-y, node))

seen = [False] * n
dist = [float('INF')] * n
todo = [(0, 0)]

while todo:
    d, node = heapq.heappop(todo)
    if seen[node]:
        continue
    seen[node] = True
    dist[node] = d

    for edge in edges[node]:
        nd, to = edge
        if dist[to] <= nd:
            continue
        heapq.heappush(todo, (nd, to))

print(sum(dist))

from heapq import heappush, heappop


class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parents[y] = x

N = int(input())
q = []
ans = 0
S = UnionFind(N)
x = []
y = []

for i in range(N):
    p,r = map(int, input().split())
    x.append([p,i])
    y.append([r,i])

x.sort()
y.sort()
for i in range(N-1):
    x1, i1 = x[i]
    y1, j1 = y[i]
    x2, i2 = x[i+1]
    y2, j2 = y[i+1]
    heappush(q, (abs(x1-x2), i1, i2))
    heappush(q, (abs(y1-y2), j1, j2))

heappush(q, (abs(x[N-1][0]-x[0][0]), x[N-1][1], x[0][1]))
heappush(q, (abs(y[N-1][0]-y[0][0]), y[N-1][1], y[0][1]))
# クラスカル法
while len(q) > 0:
    d, a, b = heappop(q)
    if S.find(a) != S.find(b):
        ans += d
        S.union(a, b)
print(ans)

import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline
import math
from heapq import heappush, heappop, heapify

def solve(n, nodes):
  xsort_nodes = sorted(nodes, key=lambda n: n[1])
  ysort_nodes = sorted(nodes, key=lambda n: n[2])
  edges = [[] for _ in range(n)]
  for i in range(n-1):
    prev_node = xsort_nodes[i]
    post_node = xsort_nodes[i+1]
    edges[prev_node[0]].append((abs(prev_node[1]-post_node[1]), post_node[0]))
  for i in range(n-1):
    prev_node = ysort_nodes[i]
    post_node = ysort_nodes[i+1]
    edges[prev_node[0]].append((abs(prev_node[2]-post_node[2]), post_node[0]))
  for i in range(1, n):
    prev_node = xsort_nodes[i-1]
    post_node = xsort_nodes[i]
    edges[post_node[0]].append((abs(prev_node[1]-post_node[1]), prev_node[0]))
  for i in range(1, n):
    prev_node = ysort_nodes[i-1]
    post_node = ysort_nodes[i]
    edges[post_node[0]].append((abs(prev_node[2]-post_node[2]), prev_node[0]))
  tree = [0]*n
  tree[0] = 1
  distance = 0
  current_edges = [*edges[0]]
  heapify(current_edges)
  while(len(current_edges)):
    d, x = heappop(current_edges)
    if tree[x]:
      continue
    distance += d
    tree[x] = 1
    for edge in edges[x]:
      heappush(current_edges, edge)
  return distance  

def main():
  n = int(input())
  nodes = []
  for i in range(n):
    x, y = map(int, input().split(' '))
    nodes.append((i, x, y))
  ans = solve(n, nodes)
  print(ans)
  

def __starting_point():
  main()
__starting_point()


import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
from operator import itemgetter
def resolve():
    N = int(input())
    XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

    G = set()
    for key in [itemgetter(1), itemgetter(2)]:
        XY.sort(key=key)
        for i in range(N - 1):
            i1, x1, y1 = XY[i]
            i2, x2, y2 = XY[i + 1]
            d = min(abs(x1 - x2), abs(y1 - y2))
            G.add((i1, i2, d))    

    A, B, W = zip(*G)
    csr = csr_matrix((W, (A, B)), shape=(N, N))
    mst = minimum_spanning_tree(csr).astype(int)
    print(mst.sum())

def __starting_point():
    resolve()
__starting_point()

n = int(input())
plots = []
for i in range(n):
    x, y = map(int, input().split())
    plots.append((x, y, i))
edges = []
plots.sort(key=lambda x: x[0])
for k in range(n-1):
    x0, _, i = plots[k]
    x1, _, j = plots[k+1]
    edges.append((x1 - x0, i, j))

plots.sort(key=lambda x: x[1])
for k in range(n-1):
    _, y0, i = plots[k]
    _, y1, j = plots[k+1]
    edges.append((y1 - y0, i, j))



par = [i for i in range(n)]
size = [1 for _ in range(n)]
rank = [0 for _ in range(n)]
def find(x):  # 木の根を求める
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        par[y] = x
        size[x] += size[y]
    else:
        par[x] = y
        size[y] += size[x]
        if rank[x] == rank[y]:
            rank[y] += 1
def same(x, y):
    return find(x) == find(y)


def kruskal():
    edges.sort()

    res = 0
    for i in range(len(edges)):
        cost, u, v = edges[i]
        if not same(u, v):
            unite(u, v)
            res += cost

    return res

print(kruskal())

from sys import stdin, setrecursionlimit
from operator import itemgetter

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
P = [0] * N
for i in range(N):
    x, y = list(map(int, input().split()))
    P[i] = (i, x, y)

edges = []
for i in (1, 2):
    P.sort(key=itemgetter(i))
    for j in range(N - 1):
        edges.append((P[j][0], P[j + 1][0], P[j + 1][i] - P[j][i]))

edges.sort(key=itemgetter(2))
uf = UnionFind(N)
ans = 0
cities = 1
for i, j, c in edges:
    if not uf.same(i, j):
        uf.union(i, j)
        ans += c
        cities += 1
        if cities == N:
            break

print(ans)


import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
    def find(self, x):
        if self.parent[x] == x:
            return x
        # path compression
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        # union by rank
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

def __starting_point():
    N = int(input())
    vs = []
    for i in range(N):
        x,y = map(int,input().split())
        vs.append((x,y,i))
    vs.sort()
    edges = []
    for k in range(1, N):
        x,y,i = vs[k]
        a,b,j = vs[k-1]
        edges.append((i, j, min(abs(x-a),abs(y-b))))
    vs.sort(key=lambda x:x[1])
    for k in range(1, N):
        x,y,i = vs[k]
        a,b,j = vs[k-1]
        edges.append((i, j, min(abs(x-a),abs(y-b))))
    uf = UnionFind(N)
    edges.sort(key=lambda x:x[2])
    ans = 0
    for i,j,w in edges:
        if not uf.same(i,j):
            uf.unite(i,j)
            ans += w
    print(ans)
__starting_point()

N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y,i))
A=sorted(A)
B=sorted(A,reverse=False, key=lambda x: x[1]) 
#print(A,B)
E=[]
for i in range(N-1):
  E.append(((A[i+1][0]-A[i][0]),A[i][2],A[i+1][2]))
  E.append(((B[i+1][1]-B[i][1]),B[i][2],B[i+1][2]))
edge=E

def kruskal():
    cost=0
    edge.sort()
    for c,u,v in edge:
        if same(u,v):
            continue
        union(u,v)
        cost+=c
    return cost

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True

def same(x, y):
    return find(x) == find(y)
par=[-1]*N
print(kruskal())

n,*xy=map(int,open(0).read().split())
x=[[xx,i] for i,xx in enumerate(xy[::2])]
y=[[yy,i] for i,yy in enumerate(xy[1::2])]
x.sort()
y.sort()
px=[[x1-x0,i0,i1] for (x0,i0),(x1,i1) in zip(x,x[1:])]
py=[[y1-y0,i0,i1] for (y0,i0),(y1,i1) in zip(y,y[1:])]
p=px+py
x=[]
y=[]
px=[]
py=[]
p.sort()
r=[i for i in range(n)]
rank=[1 for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(path):
  rx=root(path[1])
  ry=root(path[2])
  if rx==ry:
    return 0
  else:
    if rank[rx]>rank[ry]:
      r[rx]=ry
      rank[rx]+=rank[ry]
    else:
      r[ry]=rx
      rank[ry]+=rank[rx]
    return path[0]
ans=0
for i in range(len(p)):
  ans+=union(p[i])
print(ans)

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(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()))

n=int(input())
l=sorted([list(map(int,input().split()))+[i] for i in range(n)])
xs=[(x,i)for x,y,i in l]
ys=sorted([(x,i)for y,x,i in l])
edges={}
for i in range(1,n):
    a,s=xs[i-1];d,f=xs[i]
    if (s,f)in edges:
        edges[(s,f)]=min(edges[(s,f)],abs(a-d))
    else:edges[(s,f)]=abs(a-d)
    a,s=ys[i-1];d,f=ys[i]
    if (s,f)in edges:
        edges[(s,f)]=min(edges[(s,f)],abs(a-d))
    else:edges[(s,f)]=abs(a-d)
edges=sorted(edges.items(),key=lambda x:x[1])
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(n)
ans=edges[0][1]
uf.unite(*edges[0][0])
for f,c in edges:
    if uf.same(*f):continue
    uf.unite(*f)
    ans+=c
print(ans)