Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

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


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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 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.par[y] = x

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


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Kruskal(object):
    def __init__(self, graph):
        self.edge = []
        self.total = 0

        N = len(graph)
        g = graph.graph
        uf = UnionFind(N)

        Q = []
        for src, v in g.items():
            for dst, cost in v.items():
                heappush(Q, (cost, (src, dst)))

        while len(self.edge) < N - 1 and Q:
            cost, edge = heappop(Q)
            if uf.find(edge[0]) != uf.find(edge[1]):
                self.total += cost
                self.edge.append(edge)
                uf.union(*edge)


g = Graph()
for i in range(2):
    town = sorted(town, key=itemgetter(i))
    for j in range(N - 1):
        t1, t2 = town[j], town[j + 1]
        d = t2[i] - t1[i]
        g.add_edge(t1[2], t2[2], d)
print(Kruskal(g).total)


Fixed submission:
import sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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 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.par[y] = x

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

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


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

    def find(self, x):
        """
        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 と 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.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Kruskal(object):
    """
    クラスカル法による最小全域木
    O(ElogV)
    """

    def __init__(self, graph):
        self.edge = []
        self.total = 0

        N = len(graph)
        g = graph.graph
        uf = UnionFind(N)

        Q = []
        for src, v in g.items():
            for dst, cost in v.items():
                heappush(Q, (cost, (src, dst)))

        while len(self.edge) < N - 1 and Q:
            cost, edge = heappop(Q)
            if uf.find(edge[0]) != uf.find(edge[1]):
                self.total += cost
                self.edge.append(edge)
                uf.union(*edge)


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
print(Kruskal(g).total)


Fixed submission:
import sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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 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.par[y] = x

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

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


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

    def find(self, x):
        """
        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 と 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.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Kruskal(object):
    """
    クラスカル法による最小全域木
    O(ElogV)
    """

    def __init__(self, graph):
        self.edge = []
        self.total = 0

        N = len(graph)
        g = graph.graph
        uf = UnionFind(N)

        Q = []
        for src, v in g.items():
            for dst, cost in v:
                heappush(Q, (cost, (src, dst)))

        while len(self.edge) < N - 1 and Q:
            cost, edge = heappop(Q)
            if uf.find(edge[0]) != uf.find(edge[1]):
                self.total += cost
                self.edge.append(edge)
                uf.union(*edge)


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
print(Kruskal(g).total)


Fixed submission:
import sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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 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.par[y] = x

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

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


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Prim(object):
    """
    プリム法（二分ヒープ）による最小全域木
    O((E+V)logV)
    """

    def __init__(self, graph, start=0):
        self.edge = []
        self.total = 0

        g = graph.graph
        n = len(graph)
        visited = [False] * n
        visited[start] = True

        Q = []
        for v, cost in g[start]:
            heappush(Q, (cost, (start, v)))

        while Q:
            cost, e = heappop(Q)

            if visited[e[1]]:
                continue

            self.edge.append(e)
            self.total += cost
            visited[e[1]] = True

            for v, cost in g[e[1]]:
                heappush(Q, (cost, (e[1], v)))


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
p = Prim(g)
print(p.total)

Fixed submission:
import sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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 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.par[y] = x

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

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


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Prim(object):
    """
    プリム法（二分ヒープ）による最小全域木
    O((E+V)logV)
    """

    def __init__(self, graph, start=0):
        self.edge = []
        self.total = 0

        g = graph.graph
        n = len(graph)
        visited = [False] * n
        visited[start] = True

        Q = []
        for v, cost in g[start].items():
            heappush(Q, (cost, (start, v)))

        while Q:
            cost, e = heappop(Q)

            if visited[e[1]]:
                continue

            self.edge.append(e)
            self.total += cost
            visited[e[1]] = True

            for v, cost in g[e[1]].items():
                heappush(Q, (cost, (e[1], v)))


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
p = Prim(g)
print(p.total)


Fixed submission:
import sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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 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.par[y] = x

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))