Problem:
 Score : 500 points    Problem Statement 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 1 3
1 5
3 9
7 8      Sample Output 1 3  Build a road between Towns 1 and 2 , and another between Towns 2 and 3 . The total cost is 2+1=3 yen.       Sample Input 2 6
8 3
4 9
12 19
18 1
13 5
7 6      Sample Output 2 8

Solution (Python):
import sys
input = sys.stdin.readline

from heapq import heappop,heappush

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

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    
    used = [False] * n
    q = []
    
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))

Solution (Python):
from heapq import heappop,heappush

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

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    
    used = [False] * n
    q = []
    
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))

Solution (Python):
import sys
input = sys.stdin.readline

from heapq import heappop,heappush

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

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    
    used = [False] * n
    q = []
    
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))

Solution (Python):
import sys
from operator import itemgetter
import heapq

def solve():
    input = sys.stdin.readline
    N = int(input())
    town = dict()
    road = [None] * N
    roadx, roady = [None] * N, [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        town[(x, y, i)] = i
        road[i] = (x, y, i)
        roadx[i] = (x, y, i)
        roady[i] = (x, y, i)
    roadx.sort()
    roadx_id = dict()
    roady.sort(key = itemgetter(1))
    roady_id = dict()
    for i in range(N):
        roadx_id[roadx[i]] = i
        roady_id[roady[i]] = i

    visited = [False] * N
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, 0)) 
    cost = 0
    while q:
        add_cost, id = heapq.heappop(q)
        
        
        if not visited[id]:
            cost += add_cost
            visited[id] = True
            for s in range(2):
                nx = roadx_id[road[id]] + (-1) ** s 
                if 0 <= nx < N:
                    if not visited[town[roadx[nx]]]: heapq.heappush(q, (min(abs(road[id][0] - roadx[nx][0]), abs(road[id][1] - roadx[nx][1])), town[roadx[nx]]))
                
                ny = roady_id[road[id]] + (-1) ** s 
                if 0 <= ny < N:
                    if not visited[town[roady[ny]]]: heapq.heappush(q, (min(abs(road[id][1] - roady[ny][1]), abs(road[id][1] - roady[ny][1])), town[roady[ny]]))
    
    print(cost)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
N=int(input())
x,y=map(list,zip(*[list(map(int,input().split())) for i in range(N)]))
x=sorted(zip(x,range(N)))
y=sorted(zip(y,range(N)))
from heapq import heappop,heappush
qx,qy=[(10**9+1,0,0)],[(10**9+1,0,0)]
for i in range(N-1):
    heappush(qx,(x[i+1][0]-x[i][0],x[i][1],x[i+1][1]))
    heappush(qy,(y[i+1][0]-y[i][0],y[i][1],y[i+1][1]))
r=0
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
while u.size(0)<N:
    d,i,j=heappop(qx) if qx[0]<qy[0] else heappop(qy)
    if u.unite(i,j):
        r+=d
print(r)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return


def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return


def C():
    return


def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        if x < y: x, y = y, x
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = LIR(n)
    for i in range(n):
        xy[i].append(i)
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[i] = [xy[i + 1][0] - xy[i][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    for i in range(n-1):
        edg[n + i - 1] = [xy[i + 1][1] - xy[i][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return


def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return


def C():
    return


def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return True
    n = II()
    par = [i for i in range(n)]
    rank = [0] * n
    xy = LIR(n)
    for i in range(n):
        xy[i].append(i)
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[i] = [xy[i + 1][0] - xy[i][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    for i in range(n-1):
        edg[n + i - 1] = [xy[i + 1][1] - xy[i][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return


def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return


def C():
    return


def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return True
    n = II()
    par = [i for i in range(n)]
    rank = [0] * n
    xy = LIR(n)
    for i in range(n):
        xy[i].append(i)
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[i] = [xy[i + 1][0] - xy[i][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    for i in range(n-1):
        edg[n + i - 1] = [xy[i + 1][1] - xy[i][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return


def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return


def C():
    return


def D():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    
    def same(x,y):
        return root(x) == root(y)
    
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = II()
    v = LIR(n)
    l = [None for i in range(2*n-2)]
    for i in range(n):
        v[i].append(i)
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    v.sort(key = lambda x:x[0])
    for i in range(n-1):
        l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
    v.sort(key = lambda x:x[1])
    for i in range(n-1):
        l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
    l.sort(key = lambda x:x[2])
    k = 0
    ans = 0
    for i in range(2*n-2):
        x,y,c = l[i]
        if not same(x,y):
            k += 1
            ans += c
            unite(x,y)
        if k == n-1:break
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.size = n
        self.data = [-1 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def __len__(self):
        return self.size

    def root(self, i):
        """0 <= i < n"""
        if self.data[i] < 0:
            return i
        self.data[i] = self.root(self.data[i])
        return self.data[i]

    def connected(self, i, j):
        return self.root(i) == self.root(j)

    def groupsize(self, i):
        return self.sizes[self.root(i)]

    def roots(self):
        """O(n)"""
        return [i for i, v in enumerate(self.data) if v < 0]

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if (-self.data[i]) < (-self.data[j]):
            self.data[i] = j
            self.sizes[j] += self.sizes[i]
        elif (-self.data[i]) > (-self.data[j]):
            self.data[j] = i
            self.sizes[i] += self.sizes[j]
        else:
            self.data[i] += -1
            self.data[j] = i
            self.sizes[i] += self.sizes[j]


N = int(input())
XY = []
XI = []
YI = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    XI.append((x, i))
    YI.append((y, i))
XI.sort()
YI.sort()
DIJ = []
for i in range(N - 1):
    DIJ.append((XI[i+1][0] - XI[i][0], XI[i][1], XI[i+1][1]))
    DIJ.append((YI[i+1][0] - YI[i][0], YI[i][1], YI[i+1][1]))
DIJ.sort(reverse=True)
uf = UnionFind(N)
ans = 0
while len(DIJ):
    d, i, j = DIJ.pop()
    if uf.connected(i, j):
        continue
    uf.unite(i, j)
    ans += d
    if uf.groupsize(i) == N:
        break
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  
    seen = [False] * n 
    edgelist = []  
    for e in edges[0]:  
        heapq.heappush(edgelist,(e, 0))  
    seen[0] = True  
    res_edges = []  
    res = 0  
    while len(edgelist) != 0:
        minedge, start = heapq.heappop(edgelist)  
        if seen[minedge[1]]:  
            continue
        v = minedge[1]  
        seen[v] = True  
        for e in edges[v]:  
            if not seen[e[1]]:
                heapq.heappush(edgelist,(e, v))
        res_edges.append((start, v, minedge[0]))  
        res += minedge[0]  
    
    
    return res  



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    
    
    
    
    
    
    
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    
    print(prim_heap(N, edges))

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  
    seen = [False] * n 
    edgelist = []  
    for e in edges[0]:  
        heapq.heappush(edgelist,e)
    seen[0] = True  
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)  
        if seen[minedge[1]]:  
            continue
        v = minedge[1]  
        seen[v] = True  
        for e in edges[v]:  
            if not seen[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]  
    return res  



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    
    
    
    
    
    
    
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    
    print(prim_heap(N, edges))

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  
    seen = [False] * n 
    edgelist = []  
    for e in edges[0]:  
        heapq.heappush(edgelist,e)
    seen[0] = True  
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)  
        if seen[minedge[1]]:  
            continue
        v = minedge[1]  
        seen[v] = True  
        for e in edges[v]:  
            if not seen[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]  
    return res  



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    
    
    
    
    
    
    
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    
    print(prim_heap(N, edges))


main()

Solution (Python):
from heapq import heappush, heappop
import sys
from operator import itemgetter
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            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.root(x) == self.root(y)

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

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

edge = []
points.sort(key=itemgetter(0))
for i in range(1, n):
    dist = points[i][0] - points[i-1][0]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

points.sort(key=itemgetter(1))
for i in range(1, n):
    dist = points[i][1] - points[i-1][1]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))


edge.sort(key=itemgetter(2))
uf = UnionFind(n)
ans = 0
for u, v, cost in edge:
    if not uf.same(u, v):
        ans += cost
        uf.unite(u, v)
print(ans)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            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.root(x) == self.root(y)

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

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

edge = []
points.sort()
for i in range(1, n):
    dist = points[i][0] - points[i-1][0]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

points.sort(key=lambda x: x[1])
for i in range(1, n):
    dist = points[i][1] - points[i-1][1]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))


edge.sort(key=lambda x: x[2])
uf = UnionFind(n)
ans = 0
for u, v, cost in edge:
    if not uf.same(u, v):
        ans += cost
        uf.unite(u, v)
print(ans)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            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.root(x) == self.root(y)

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

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

edge = []
points.sort()
for i in range(1, n):
    dist = points[i][0] - points[i-1][0]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

points.sort(key=lambda x: x[1])
for i in range(1, n):
    dist = points[i][1] - points[i-1][1]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))


edge.sort(key=lambda x: x[2])
uf = UnionFind(n)
ans = 0
for u, v, cost in edge:
    if not uf.same(u, v):
        ans += cost
        uf.unite(u, v)
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.count = [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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]
import sys
input = sys.stdin.readline
n = int(input())
data = [list(map(int,input().split()))+[i] for i in range(n)]

data.sort()
edge = []
append = edge.append
for i in range(1,n):
    append([data[i][0]-data[i-1][0],data[i][2],data[i-1][2]])
data.sort(key=lambda x:x[1])
for i in range(1,n):
    append([data[i][1]-data[i-1][1],data[i][2],data[i-1][2]])

edge.sort()
uf = UnionFind(n)
ans = 0
for x,y,z in edge:
    if not uf.same_check(y,z):
        uf.union(y,z)
        ans += x

print(ans)

Solution (Python):
N = int(input())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
Isx = sorted(range(N), key=lambda i: (xys[i][0], xys[i][1]))
Isy = sorted(range(N), key=lambda i: (xys[i][1], xys[i][0]))


M = set()
for i in range(1, N):
  p, q = Isx[i-1], Isx[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
for i in range(1, N):
  p, q = Isy[i-1], Isy[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))

S = list(M)
S.sort(reverse=True)

r = 0
UF = list(range(N))
def par(m):
  if UF[m] == m:
    return m
  ret = par(UF[m])
  UF[m] = ret
  return ret
while S:
  cost, p, q = S.pop()
  i = par(p)
  j = par(q)
  if i != j:
    r += cost
    UF[i] = j
  
print(r)

Solution (Python):
from heapq import heappush, heappop


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


graph = [[] for i in range(n)]


coordinate_list.sort(key = lambda x: x[1][0])
for i in range(n - 1):
    cost = coordinate_list[i + 1][1][0] - coordinate_list[i][1][0]
    graph[coordinate_list[i][0]] += [(cost, coordinate_list[i+1][0])]
    graph[coordinate_list[i + 1][0]] += [(cost, coordinate_list[i][0])]


coordinate_list.sort(key = lambda x: x[1][1])
for i in range(n - 1):
    cost = coordinate_list[i + 1][1][1] - coordinate_list[i][1][1]
    graph[coordinate_list[i][0]] += [(cost, coordinate_list[i+1][0])]
    graph[coordinate_list[i + 1][0]] += [(cost, coordinate_list[i][0])]


is_used = [0] * n
que = []
ret = 0
heappush(que, (0, 0))


for i in range(n):
    while True:
        add_cost, add_v = heappop(que)
        if not is_used[add_v]:
            break
    is_used[add_v] = 1
    ret += add_cost
    for cost, to_v in graph[add_v]:
        if not is_used[to_v]:
            heappush(que, (cost, to_v))


print(ret)