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):
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        
        
        
        C = {}
        dp = defaultdict(int)

        
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        
        
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        
        bits = (2 ** n - 1) - 1

        
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    loop = 2**M
    dp = [inf]*loop
    dp[0] = 0
    cnt = Counter(A)
    L = [0]*loop
    
    for i in range(loop):
        for j in range(M):
            if i&(1<<j)==(1<<j):
                continue
            next = i|(1<<j)
            if L[next]==0:
                L[next] = L[i]+cnt[j]
            cur = imos[j][L[next]] - imos[j][L[i]]
            if dp[next]>dp[i] + cur:
                dp[next] = dp[i] + cur
    ans = dp[-1]
    
    print(ans)
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    def dijkstra_2(edge_adj, node, start):
        
        
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    V = [[inf]*N for _ in range(N)]
    ans = []
    for _ in range(K):
        A = LI()
        s = A[1]-1
        t = A[2]-1
        if A[0]==1:
            if V[s][t] <= A[3]:
                continue
            V[s][t] = A[3]
            V[t][s] = A[3]
        else:
            dist = dijkstra_2(V,N,s)
            ans.append(dist[t])
    for v in ans:
        if v==inf:
            print(-1)
            continue
        print(v)
    return

def JOI15_E():
    def bfs(n, E, fordfs):
        
        W = [inf] * n
        
        que = deque()
        for e in E:
            e -=1
            W[e] = 0
            que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] > nowW + 1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M, K, S = LI()
    P, Q = LI()
    C = [I()for _ in range(K)]
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t = LI()
        s -= 1
        t -= 1
        V[s].append(t)
        V[t].append(s)
    L = bfs(N,C,V)
    
    cost = [[]for _ in range(N)]
    for i in range(N):
        for v in V[i]:
            if L[v]==0:
                continue
            elif L[v]<=S:
                cost[i].append((v,Q))
            else:
                cost[i].append((v,P))
    di = Dijkstra(cost)
    ans = di.dist
    
    if L[-1]<=S:
        print(ans[N-1]-Q)
    else:
        print(ans[N-1]-P)
    return

def JOI13_E():
    def bfs(n, e, fordfs):
        
        W = [inf] * n
        
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == inf:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    def dijkstra_2(edge_adj, node, start):
        
        
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    C = [[]for _ in range(N)]
    V = [[]for _ in range(N)]
    for i in range(N):
        C[i] = LI()
    for i in range(K):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    costV = [[inf]*N for _ in range(N)]
    for i in range(N):
        L = bfs(N,i,V)
        c = C[i][0]; l = C[i][1]
        for j in range(N):
            if i==j:
                continue
            if L[j]<=l:
                costV[i][j] = c
    dist = dijkstra_2(costV,N,0)
    ans = dist[N-1]
    
    print(ans)
    return

def ABC12_D():
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N, M = LI()
    V = [[inf]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for _ in range(M):
        a, b, t = LI()
        a -= 1
        b -= 1
        V[a][b] = t
        V[b][a] = t
    L = warshall_floyd(N,V)
    
    ans = inf
    for i in range(N):
        cur = max(L[i])
        ans = min(ans,cur)
    print(ans)
    return

def ABC79_D():
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    H, W = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    L = warshall_floyd(10,C)
    
    ans = 0
    for a in A:
        for i in a:
            if i>=0:
                ans += L[i][1]
    print(ans)
    return

def JOIgassyuku10_3():
    N, M, K = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b, c = LI()
        a -= 1
        b -= 1
        V[a].append((b,c))
        V[b].append((a,c))


    return

def ABC74_D():
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N = I()
    A = [LI() for _ in range(N)]
    dist = warshall_floyd(N,copy.deepcopy(A))
    shortest_path = 0
    for i in range(N):
        for j in range(N):
            if i==j:
                continue
            if dist[i][j]<A[i][j]:
                print(-1)
                return
            if dist[i][j]>A[i][j]:
                continue
            flag = True
            for k in range(N):
                if i==k or j==k:
                    continue
                judge = (dist[i][k]+dist[k][j])-dist[i][j]
                if judge==0:
                    flag = False
            if flag:
                shortest_path += A[i][j]
    ans = shortest_path//2
    print(ans)
    return

def ABC65_D():
    class Kruskal_UnionFind():
        
        def __init__(self, N):
            self.edges = []
            self.rank = [0] * N
            self.par = [i for i in range(N)]
            self.counter = [1] * N

        def add(self, u, v, d):
            """
            u = from, v = to, d = cost
            """
            self.edges.append([u, v, d])

        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:
                z = self.counter[x] + self.counter[y]
                self.counter[x], self.counter[y] = z, z
            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 size(self, x):
            x = self.find(x)
            return self.counter[x]

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

        def Kruskal(self):
            """
            return: 最小全域木のコストの和
            """
            edges = sorted(self.edges, key=lambda x: x[2])  
            res = 0
            for e in edges:
                if not self.same(e[0], e[1]):
                    self.unite(e[0], e[1])
                    res += e[2]
            return res
    N = I()
    X = []
    for i in range(N):
        a, b = LI()
        X.append((a,b))
    P = defaultdict(set)
    for i,x in enumerate(X):
        P[x] = i
    graph = Kruskal_UnionFind(N + 1)

    X.sort(key=lambda x:x[0])
    for i in range(N-1):
        if X[i+1][0]-X[i][0]>abs(X[i+1][1]-X[i][1]):
            continue
        r = X[i+1][0]-X[i][0]
        graph.add(P[X[i]], P[X[i+1]], r)

    X.sort(key=lambda x:x[1])
    for i in range(N-1):
        if X[i+1][1]-X[i][1]>abs(X[i+1][0]-X[i][0]):
            continue
        r = X[i+1][1]-X[i][1]
        graph.add(P[X[i]], P[X[i+1]], r)
    
    ans = graph.Kruskal()
    print(ans)
    return



def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

import gc
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC65_D()
"""

"""

Solution (Python):
import heapq



N = int(input())
xy = [None] * N
yx = [None] * N

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


xy.sort()
yx.sort()


es = [[] for _ in range(N)]
for i in range(N-1):
    heapq.heappush(es[xy[i][2]], (abs(xy[i][0] - xy[i+1][0]), xy[i+1][2]))
    heapq.heappush(es[xy[i+1][2]], (abs(xy[i][0] - xy[i+1][0]), xy[i][2]))

    heapq.heappush(es[yx[i][2]], (abs(yx[i][0] - yx[i+1][0]), yx[i+1][2]))
    heapq.heappush(es[yx[i+1][2]], (abs(yx[i][0] - yx[i+1][0]), yx[i][2]))


used = [False] * N
used[0] = True
ans = 0

q = []
for c,nxt in es[0]:
    heapq.heappush(q, (c, nxt))

while q:
    c, curr = heapq.heappop(q)
    
    if used[curr]:
        continue

    used[curr] = True
    for nc, nxt in es[curr]:
        if not used[nxt]:
            heapq.heappush(q, (nc, nxt))
    ans += c

print(ans)

Solution (Python):
import heapq


class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * 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.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
        self.count += 1

N = int(input())
xy = [None] * N
yx = [None] * N

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


xy.sort()
yx.sort()


q = []
for i in range(N-1):
    heapq.heappush(q, (abs(xy[i][0] - xy[i+1][0]), xy[i][2], xy[i+1][2]))
    heapq.heappush(q, (abs(yx[i][0] - yx[i+1][0]), yx[i][2], yx[i+1][2]))

uf = UnionFind(N)
ans = 0

while q:
    c, a, b = heapq.heappop(q)
    if not uf.is_same(a,b):
        uf.unite(a, b)
        ans += c

print(ans)

Solution (Python):
from operator import itemgetter


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[y] < self.parents[x]:
            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())


def solve():
    N = int(input())
    xy = [list(map(lambda x: int(x) - 1, input().split())) + [i] for i in range(N)]
    
    sorted_x = sorted(xy, key=itemgetter(0, 1))
    sorted_y = sorted(xy, key=itemgetter(1, 0))
    edges = []
    for i in range(N - 1):
        cost = min(abs(sorted_x[i][0] - sorted_x[i + 1][0]), abs(sorted_x[i][1] - sorted_x[i + 1][1]))
        edges.append([cost, sorted_x[i][2], sorted_x[i + 1][2]])
        cost = min(abs(sorted_y[i][0] - sorted_y[i + 1][0]), abs(sorted_y[i][1] - sorted_y[i + 1][1]))
        edges.append([cost, sorted_y[i][2], sorted_y[i + 1][2]])
    edges.sort(key=itemgetter(0))
    
    ans = 0
    uf_tree = UnionFind(N)
    for cost, u, v in edges:
        if not uf_tree.same(u, v):
            ans += cost
            uf_tree.union(u, v)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
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())
      
n = int(input())
XY = [tuple(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
L_to_R = sorted([(x, i) for i, x in enumerate(X)])
D_to_U = sorted([(y, i) for i, y in enumerate(Y)])
dist = []
for i in range(n-1):
  x1, num1 = L_to_R[i]
  x2, num2 = L_to_R[i+1]
  d = x2-x1
  dist.append((d, num1, num2))
for i in range(n-1):
  y1, num1 = D_to_U[i]
  y2, num2 = D_to_U[i+1]
  d = y2-y1
  dist.append((d, num1, num2))
dist.sort(reverse=True)  
  
uf = UnionFind(n)
count = 0
ans = 0
while count < n-1:
  d, num1, num2 = dist.pop()
  if uf.same(num1, num2):
    continue
  count += 1
  ans += d
  uf.unite(num1, num2)
print(ans)

Solution (Python):
from operator import itemgetter

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())
      
n = int(input())
XY = [tuple(map(int, input().split())) for _ in range(n)]
L_to_R = sorted([(xy[0], xy[1], i) for i, xy in enumerate(XY)])
D_to_U = sorted([(xy[0], xy[1], i) for i, xy in enumerate(XY)], key=itemgetter(1))
dist = []
for i in range(n-1):
  x1, y1, num1 = L_to_R[i]
  x2, y2, num2 = L_to_R[i+1]
  d = min(abs(x1-x2), abs(y1-y2))
  dist.append((d, num1, num2))
for i in range(n-1):
  x1, y1, num1 = D_to_U[i]
  x2, y2, num2 = D_to_U[i+1]
  d = min(abs(x1-x2), abs(y1-y2))
  dist.append((d, num1, num2))
dist.sort(reverse=True)  
  
uf = UnionFind(n)
count = 0
ans = 0
while count < n-1:
  d, num1, num2 = dist.pop()
  if uf.same(num1, num2):
    continue
  count += 1
  ans += d
  uf.unite(num1, num2)
print(ans)

Solution (Python):



from heapq import *






N=int(input())

Xsort=[]
Ysort=[]
for i in range(N):
    X,Y=map(int,input().split())
    Xsort.append([X,i])
    Ysort.append([Y,i])
Xsort=sorted(Xsort,key=lambda x:x[0])
Ysort=sorted(Ysort,key=lambda x:x[0])
Nidxlst=[[0,0] for i in range(N)]
for i in range(N):
    idx=Xsort[i][1]
    Nidxlst[idx][0]=i
    idx=Ysort[i][1]
    Nidxlst[idx][1]=i



value=0
x,y=Nidxlst[0]
ittenai=set([i for i in range(1,N)])

stack=[]
heapify(stack)
setm=set()
dic={}
def main(x,y):
    if x>0:
        a=Xsort[x-1][1]
        if a in ittenai:
            m=Xsort[x][0]-Xsort[x-1][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
    if x<N-1:
        a=Xsort[x+1][1]
        if a in ittenai:
            m=Xsort[x+1][0]-Xsort[x][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
    if y>0:
        a=Ysort[y-1][1]
        if a in ittenai:
            m=Ysort[y][0]-Ysort[y-1][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
    if y<N-1:
        a=Ysort[y+1][1]
        if a in ittenai:
            m=Ysort[y+1][0]-Ysort[y][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
main(x,y)
idle=10**9+1
value=0
while ittenai:
    m=heappop(stack)
    a=dic[m].pop()
    if a in ittenai:
        x,y=Nidxlst[a]
        main(x,y)
        ittenai.remove(a)
        value+=m

print(value)

Solution (Python):
import sys
from collections import deque
import heapq
import bisect
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
xy = [tuple([int(x) for x in input().strip().split()] + [n+1]) for n in range(N)]
x_sorted = sorted(xy)
y_sorted = sorted(xy, key=lambda x: x[1])
L = [deque([]) for _ in range(N)]
L[x_sorted[0][2]-1].append((x_sorted[1][2], x_sorted[1][0]-x_sorted[0][0]))
L[y_sorted[0][2]-1].append((y_sorted[1][2], y_sorted[1][1]-y_sorted[0][1]))
for n in range(1, N-1):
    L[x_sorted[n][2]-1].append((x_sorted[n-1][2], x_sorted[n][0]-x_sorted[n-1][0]))
    L[x_sorted[n][2]-1].append((x_sorted[n+1][2], x_sorted[n+1][0]-x_sorted[n][0]))
    L[y_sorted[n][2]-1].append((y_sorted[n-1][2], y_sorted[n][1]-y_sorted[n-1][1]))
    L[y_sorted[n][2]-1].append((y_sorted[n+1][2], y_sorted[n+1][1]-y_sorted[n][1]))
L[x_sorted[-1][2]-1].append((x_sorted[-2][2], x_sorted[-1][0]-x_sorted[-2][0]))
L[y_sorted[-1][2]-1].append((y_sorted[-2][2], y_sorted[-1][1]-y_sorted[-2][1]))


q = [(0, 1)]
cost = [float('inf')] * N

while q:
    c, p = heapq.heappop(q)
    if cost[p-1] <= c:
        continue
    cost[p-1] = c
    for np, nc in L[p-1]:
        if cost[np-1] == float('inf') and cost[np-1] > c + nc:
            heapq.heappush(q, (nc, np))

print(sum(cost))

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def ufinit(n):
  global ufsz, ufances
  ufsz = [1] * n
  ufances = [0] * n
  for i in range(n):
    ufances[i] = i

def ufroot(x):
  global ufances
  a = []
  y = x
  while ufances[y] != y:
    a.append(y)
    y = ufances[y]
  for z in a:
    ufances[z] = y
  return y

def ufconn(x,y):
  global ufsz, ufances
  i = ufroot(x)
  j = ufroot(y)
  if i==j:
    return
  
  k  = j if (ufsz[i]<ufsz[j]) else i
  if k==j:
    ufances[i] = j
  else:
    ufances[j] = i
  ufsz[k] = ufsz[i] + ufsz[j]

n = inn()
x = []
y = []
for i in range(n):
    xx,yy = inm()
    x.append((xx,i))
    y.append((yy,i))
x.sort()
y.sort()
dx = []
dy = []
for i in range(n-1):
    dx.append((abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]))
    dy.append((abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]))
dx.sort(reverse=True)
dy.sort(reverse=True)
ufinit(n)
dxt = dx.pop()
dyt = dy.pop()
sm = 0
while dxt and dyt:
    
    
    if dxt[0]<dyt[0]:
        if ufroot(dxt[1])!=ufroot(dxt[2]):
            sm += dxt[0]
            ufconn(dxt[1],dxt[2])
        dxt = False if len(dx)==0 else dx.pop()
    else:
        if ufroot(dyt[1])!=ufroot(dyt[2]):
            sm += dyt[0]
            ufconn(dyt[1],dyt[2])
        dyt = False if len(dy)==0 else dy.pop()
print(sm)

Solution (Python):
from heapq import heappop, heappush


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  

    def find(self, x):
        while self.tree[x] != self.tree[self.tree[x]]:
            self.tree[x] = self.tree[self.tree[x]]  
        return self.tree[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.tree[x] = y
            self.size[y] += self.size[x]
        else:
            self.tree[y] = x
            self.size[x] += self.size[y]

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

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


def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


N = I()
X = [None] * N
Y = [None] * N
for i in range(N):
    x, y = MI()
    X[i] = (x, i, x, y)
    Y[i] = (y, i, x, y)
X.sort()
Y.sort()


q = list()
for i in range(N - 1):
    for axis in [X, Y]:
        _, t0, x0, y0 = axis[i]
        _, t1, x1, y1 = axis[i + 1]
        cost = min(abs(x1 - x0), abs(y1 - y0))
        heappush(q, (cost, t0, t1))


uf = UnionFind(N)
ans = 0
while len(q) > 0:
    cost, t0, t1 = heappop(q)
    if not uf.has_same_parent(t0, t1):
        uf.unite(t0, t1)
        ans += cost
print(ans)

Solution (Python):

n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = []
for j in range(n-1):
  road.append([xyi[j+1][0]-xyi[j][0],xyi[j][2],xyi[j+1][2]])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  road.append([xyi[j+1][1]-xyi[j][1],xyi[j][2],xyi[j+1][2]])
road.sort()
pre = [i for i in range(n)]
ans = 0
for k in range(2*n-2):
  d,I,J = road[k]
  ii = []
  jj = []
  while pre[I] != I:
    ii.append(I)
    I = pre[I]
  for Is in ii:
    pre[Is] = I
  while pre[J] != J:
    jj.append(J)
    J = pre[J]
  for Js in jj:
    pre[Js] = J
  if I != J:
    pre[J] = I
    ans += d
print(ans)