#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mo 1000000007 
using namespace std;
int n,i,x[1000005],y[1000005],top,l,r,mid,max1,ll,rr;
int p1,p2,p3,lx[1000005],rx[1000005],ly[1000005],ry[1000005];
int bookx[1000005],booky[1000005],zz[1000005],top3;
int topx,topy,top2,nex[3000005],to[3000005],fir[1000005];
int flag,book[1000005],book2[1000005],zhan[1000005];
struct nyh{
	int p,id;
}o[1000005];
int zzz(int z){
	if(zz[z]==z) return z;
	return zz[z]=zzz(zz[z]);
}
int lj(int u,int v){
	top2++;
	nex[top2]=fir[u];
	fir[u]=top2;
	to[top2]=v;
}
int x1tree(int u,int v,int w){
	int mid2=((u+v)>>1);
	if(u==v){
		bookx[o[v].id]=w;
		return 0;
	}
	topx++;
	lx[w]=topx;
	lj(topx,w);
	topx++;
	rx[w]=topx;
	lj(topx,w);
	x1tree(u,mid2,lx[w]);
	x1tree(mid2+1,v,rx[w]);
}
int y1tree(int u,int v,int w){
	int mid2=((u+v)>>1);
	if(u==v){
		if(o[v].id<=n)
			booky[o[v].id+n]=w;
		else
			booky[o[v].id-n]=w;
		return 0;
	}
	topy++;
	ly[w]=topy;
	lj(w,topy);
	topy++;
	ry[w]=topy;
	lj(w,topy);
	y1tree(u,mid2,ly[w]);
	y1tree(mid2+1,v,ry[w]);
}
int x2tree(int u,int v,int w){
	int mid2=((u+v)>>1);
	if(p1<=u&&v<=p2){
		lj(w,p3);
		return 0;
	}
	if(p1<=mid2&&p2>=u) x2tree(u,mid2,lx[w]);
	if(p1<=v&&p2>=mid2+1) x2tree(mid2+1,v,rx[w]);
}
int y2tree(int u,int v,int w){
	int mid2=((u+v)>>1);
	if(p1<=u&&v<=p2){
		lj(p3,w);
		return 0;
	}
	if(p1<=mid2&&p2>=u) y2tree(u,mid2,ly[w]);
	if(p1<=v&&p2>=mid2+1) y2tree(mid2+1,v,ry[w]);
}
int ss(int v){
	book[v]=1;
	top3++;
	zhan[top3]=v;
	book2[v]=1;
	for(int top1=fir[v];top1;top1=nex[top1]){
		if(book[to[top1]]==0)
			ss(to[top1]);
		else if(book2[zzz(to[top1])]==1){
			int p=zzz(to[top1]);
			while(zhan[top3]!=p){
				zz[zzz(zhan[top3])]=p;
				book2[zhan[top3]]=0;
				zhan[top3]=0;
				top3--;
			}
		}
	}
	if(zhan[top3]==v){
		zhan[top3]=0;
		top3--;
	}
	book2[v]=0;
}
bool cmp(nyh u,nyh v){
	return u.p<v.p;
}
int read(){
	int xx=0,flag2=1;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')
		ch=getchar();
	if(ch=='-'){
		flag2=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		xx=xx*10+ch-'0';
		ch=getchar();
	}
	return flag2*xx;
}
int main(){
	n=read();
	for(i=1;i<=n;i++){
		x[i]=read();
		top++;
		o[top].p=x[i];
		o[top].id=i;
		y[i]=read();
		top++;
		o[top].p=y[i];
		o[top].id=i+n;
	}
	sort(o+1,o+top+1,cmp);
	l=1;r=1000000000;mid=((l+r)>>1);
	while(l<=r){
		ll=1;rr=1;
		topx=top+1;
		x1tree(1,top,topx);
		topy=topx+1;
		y1tree(1,top,topy);
		for(i=1;i<=top;i++){
			lj(bookx[i],booky[i]);
			lj(booky[i],bookx[i]);
		}
		for(i=1;i<=top;i++){
			while(o[rr+1].p-o[i].p<=mid-1&&rr<top)
				rr++;
			while(o[i].p-o[ll].p>=mid)
				ll++;
			p1=ll;p2=i-1;
			if(o[i].id<=n)
				p3=booky[o[i].id+n];
			else
				p3=booky[o[i].id-n];
			if(p1<=p2)
				x2tree(1,top,top+1);
			p1=i+1;p2=rr;
			if(o[i].id<=n)
				p3=booky[o[i].id+n];
			else
				p3=booky[o[i].id-n];
			if(p1<=p2)
				x2tree(1,top,top+1);
			p1=ll;p2=i-1;p3=bookx[o[i].id];
			if(p1<=p2)
				y2tree(1,top,topx+1);
			p1=i+1;p2=rr;p3=bookx[o[i].id];
			if(p1<=p2)
				y2tree(1,top,topx+1);
		}
		for(i=1;i<=topy;i++)
			zz[i]=i;
		for(i=1;i<=topy;i++)
			if(book[i]==0)
				ss(i);
		flag=0;
		for(i=1;i<=n;i++)
			if(zzz(bookx[i])==zzz(bookx[i+n]))
				flag=1;
		for(i=1;i<=top2;i++){
			nex[i]=0;
			to[i]=0;
		}
		for(i=1;i<=topy;i++){
			book[i]=0;
			book2[i]=0;
			bookx[i]=0;
			booky[i]=0;
			fir[i]=0;
			zz[i]=0;
			lx[i]=0;
			rx[i]=0;
			ly[i]=0;
			ry[i]=0;
			zhan[i]=0;
		}
		top2=0;
		topx=0;
		topy=0;
		if(flag==1)
			r=mid-1;
		else{
			l=mid+1;
			max1=max(max1,mid);
		}
		mid=((l+r)>>1);
	}
	cout<<max1<<endl;
	return 0;
}

Measured memory_bytes: 49408