#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
typedef long long s64;
 
const int ONE = 2000005;
const int INF = 1e9;
 
#define next nxt
 
int get()
{
		int res = 1, Q = 1; char c;
		while( (c = getchar()) < 48 || c > 57)
			if(c == '-') Q = -1;
		if(Q) res = c - 48;
		while( (c = getchar()) >= 48 && c <= 57)
			res = res * 10 + c - 48;
		return res * Q;
}
 
int Dfn[ONE], Low[ONE], Time_cnt;
int top, stk[5000005], vis[ONE];
int F[ONE], scc;
 
int next[10000005], first[ONE], go[10000005], tot;
 
void Add(int u, int v)
{
		next[++tot] = first[u], first[u] = tot, go[tot] = v;
}
 
void Tarjan(int u)
{
		Dfn[u] = Low[u] = ++Time_cnt;
		vis[u] = 1, stk[++top] = u;
		for(int e = first[u]; e; e = next[e])
		{
			int v = go[e];
			if(!Dfn[v])
			{
				Tarjan(v);
				Low[u] = min(Low[u], Low[v]);
			}
			else if(vis[v])
			Low[u] = min(Low[u], Dfn[v]);
		}
 
		int v;
		if(Low[u] == Dfn[u])
		{
			scc++;
			do
			{
				v = stk[top--];
				vis[v] = 0;
				F[v] = scc;
			}while(v != u);
		}
}
 
struct point {int x, y;} a[ONE];
struct power {int a, b;} A[ONE];
int n;
 
int cnt = 0;
int lc[ONE], rc[ONE];
int root;
vector <int> Node[ONE];
 
void Update(int &i, int l, int r, int L, int id)
{
		if(!i) i = ++cnt;
		Node[i].push_back(id);
		if(l == r) return;
		int mid = l + r >> 1;
		if(L <= mid) Update(lc[i], l, mid, L, id);
		else Update(rc[i], mid + 1, r, L, id);
}
 
int Limit = 250;
int num;

void Query(int i, int l, int r, int L, int R, int id, int dist)
{
		if(!i) return;
		if(num > Limit) return;
		if(L <= l && r <= R)
		{
			for(int k = 0; k < Node[i].size(); k++)
			{
				int j = Node[i][k];
				if(abs(a[id].x - a[j].x) < dist) Add(A[id].a, A[j].b), Add(A[j].a, A[id].b), num++;
				if(abs(a[id].x - a[j].y) < dist) Add(A[id].a, A[j].a), Add(A[j].b, A[id].b), num++;
				if(abs(a[id].y - a[j].x) < dist) Add(A[id].b, A[j].b), Add(A[j].a, A[id].a), num++;
				if(abs(a[id].y - a[j].y) < dist) Add(A[id].b, A[j].a), Add(A[j].b, A[id].a), num++;
				if(num > Limit) break;
			}
			return;
		}
		int mid = l + r >> 1;
		if(L <= mid) Query(lc[i], l, mid, L, R, id, dist);
		if(mid + 1 <= R) Query(rc[i], mid + 1, r, L, R, id, dist);
}
 
int Check(int dist)
{
		top = Time_cnt = scc = tot = 0;
		for(int i = 1; i <= 2 * n; i++) Dfn[i] = Low[i] = vis[i] = first[i] = 0;
 
		for(int i = 1; i <= cnt; i++) lc[i] = rc[i] = 0, Node[i].clear();
		cnt = root = 0;
		for(int i = 1; i <= n; i++)
		{
			num = 0;
			Query(root, 1, INF, a[i].x - dist, a[i].x + dist, i, dist);
			Query(root, 1, INF, a[i].y - dist, a[i].y + dist, i, dist);
			Update(root, 1, INF, a[i].x, i);
			Update(root, 1, INF, a[i].y, i);
		}
 
		for(int i = 1; i <= 2 * n; i++) if(!Dfn[i]) Tarjan(i);
		for(int i = 1; i <= n; i++) if(F[A[i].a] == F[A[i].b]) return 0;
		return 1;
}
 
int main()
{
		//freopen(".in","r",stdin);
		//freopen(".out","w",stdout);
		n = get();
		for(int i = 1; i <= n; i++)
			a[i].x = get(), a[i].y = get(),
			A[i].a = i, A[i].b = i + n;
 
		int l = 0, r = INF;
		while(l < r - 1)
		{
			int mid = l + r >> 1;
			if(Check(mid)) l = mid;
			else r = mid;
		}
		if(Check(r)) printf("%d", r);
		else printf("%d", l);
}

Measured memory_bytes: 127744