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.

Source: atcoder | Difficulty: MEDIUM_HARD


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

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


import sys

class UnionFind:

	def __init__(self, n):
		self.n = n
		self._root_table = list(range(n))
		self._size_table = [1] * n

	def find(self, x):
		r = self._root_table[x]
		if r != x:
			r = self._root_table[x] = self.find(r)
		return r

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		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:

	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):
	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)
	if used[v]:
		continue
	used[v] = 1
	ans += cv
	for (w, c) in adj[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]
	heappush(H, (x2 - x1, j1, j2))
	heappush(H, (y2 - y1, k1, k2))
answer = 0
data = [-1] * (N + 1)
height = [0] * (N + 1)
while H:
	(w, s, t) = heappop(H)
	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())


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))])
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):
		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

	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
		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()
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)))
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()
	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
	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_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)])
	mst_cost = kruskal(edge, N)
	print(mst_cost)

def __starting_point():
	resolve()
__starting_point()


class union_find:

	def __init__(self, N):
		self.par = [-1] * N

	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 unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return False
		else:
			if self.par[x] > self.par[y]:
				(x, y) = (y, x)
			self.par[x] += self.par[y]
			self.par[y] = x
			return True

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

	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 = 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:])
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'])
Root = [root(i, 0) for i in range(N)]

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

def unionT(i, j):
	(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

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):
	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)
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))
	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):
	costs = defaultdict(int)
	costs_defined = defaultdict(int)
	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
	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
	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)


import sys
import heapq
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))
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):
		(x[i], y[i]) = list(map(int, input().split()))
elif icase == 1:
	n = 3
	x = [1, 3, 7]
	y = [5, 9, 8]
elif icase == 2:
	n = 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)
	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(length_sum)


def find(x):
	if par[x] < 0:
		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 False
	else:
		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)

def size(x):
	return -par[find(x)]
n = int(input())
par = [-1] * n
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])
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)


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
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)

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)


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
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()))
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
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)


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)


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()
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]))
		node[xy[i + 1][0]].append((abs(xy[i][1] - xy[i + 1][1]), xy[i][0]))
	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]))
		node[xy[i + 1][0]].append((abs(xy[i][2] - xy[i + 1][2]), xy[i][0]))
	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:

	def __init__(self, n):
		self.N = n
		self.parent = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]

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

def clascal(N, E, tree_count=1):
	tree = UnionFind(N)
	weight = 0
	counter = 0
	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 = []
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))
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))


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


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
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 = []
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))
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.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])
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])
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)


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


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

	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:

	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
		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
		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])
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 = 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:
	__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)