#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<utility>
#include<climits>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define N 500010
#define M 5000010
#define gc getchar()
#define INF (INT_MAX/2-10)
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
inline int inn()
{
	int x,ch;while((ch=gc)<'0'||ch>'9');
	x=ch^'0';while((ch=gc)>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^'0');return x;
}
struct edges{
	int to,pre;
}e[M];int h[N],etop,x[N],y[N],xs[N],ys[N],hs[N],etops,pre[N];
int sta[N],bel[N],low[N],dfn[N],nc,dfc,P[N],Q[N],lfid[N],suf[N];
vector<int> vc;vector<pii> tp[N];stack<int> s;int cc;
inline int add_edge(int u,int v) { return /*debug(u)sp,debug(v)ln,*/e[++etop].to=v,e[etop].pre=h[u],h[u]=etop; }
inline int getid(int x) { return lower_bound(vc.begin(),vc.end(),x)-vc.begin()+1; }
struct segment{
	int l,r,id;segment *ch[2];
}*rt;
int build(segment* &rt,int l,int r)
{
	rt=new segment,rt->l=l,rt->r=r,rt->id=++nc;
//	debug(l)sp,debug(r)sp,debug(nc)ln;
	if(l==r) return lfid[l]=nc;int mid=(l+r)/2;
	add_edge(rt->id,build(rt->ch[0],l,mid));
	add_edge(rt->id,build(rt->ch[1],mid+1,r));
	return rt->id;
}
int LB(segment* &rt,int x,int s,int t)
{
	if(s>t) return 0;
	int l=rt->l,r=rt->r,mid=(l+r)>>1;
	if(s<=l&&r<=t) return add_edge(x,rt->id);
	if(s<=mid) LB(rt->ch[0],x,s,t);
	if(mid<t) LB(rt->ch[1],x,s,t);
	return 0;
}
int tarjan(int x)
{
	s.push(x),sta[x]=1,low[x]=dfn[x]=++dfc;
	for(int i=h[x],y;i;i=e[i].pre)
		if(!sta[y=e[i].to]) tarjan(y),low[x]=min(low[x],low[y]);
		else if(sta[y]==1) low[x]=min(low[x],dfn[y]);
	if(low[x]==dfn[x])
	{
		cc++,bel[x]=cc,sta[x]=2;int y;
		while(s.top()^x) bel[y=s.top()]=cc,sta[y]=2,s.pop();
		s.pop();
	}
	return 0;
}
inline int check(int n,int d)
{
	memcpy(h,hs,sizeof(int)*(nc+1)),etop=etops;
	memset(sta,0,sizeof(int)*(nc+1)),dfc=0,cc=0;
	while(!s.empty()) s.pop();
	for(int i=1,l,r;i<=n;i++)
		l=getid(xs[i]-d+1),r=upper_bound(vc.begin(),vc.end(),xs[i]-1)-vc.begin(),LB(rt,P[i],l,r),
		l=getid(xs[i]+1),r=upper_bound(vc.begin(),vc.end(),xs[i]+d-1)-vc.begin(),LB(rt,P[i],l,r),
		l=getid(ys[i]-d+1),r=upper_bound(vc.begin(),vc.end(),ys[i]-1)-vc.begin(),LB(rt,Q[i],l,r),
		l=getid(ys[i]+1),r=upper_bound(vc.begin(),vc.end(),ys[i]+d-1)-vc.begin(),LB(rt,Q[i],l,r);
	for(int i=1;i<=nc;i++) if(!sta[i]) tarjan(i);
	for(int i=1;i<=n;i++) if(bel[P[i]]==bel[Q[i]]) return 0;
	return 1;
}
int main()
{
	int n=inn();
	for(int i=1;i<=n;i++) xs[i]=x[i]=inn(),ys[i]=y[i]=inn(),
		vc.push_back(x[i]),vc.push_back(y[i]);
	sort(vc.begin(),vc.end()),vc.push_back(INF);
	vc.erase(unique(vc.begin(),vc.end()),vc.end());
	for(int i=1;i<=n;i++) x[i]=getid(x[i]),y[i]=getid(y[i]);
//	for(int i=1;i<=n;i++) debug(i)sp,debug(x[i])sp,debug(y[i])ln;
	for(int i=1;i<=n;i++) P[i]=++nc,Q[i]=++nc;
	for(int i=1;i<=n;i++)
		tp[x[i]].pb(mp(P[i],Q[i])),
		tp[y[i]].pb(mp(Q[i],P[i]));
	for(int i=1;i<=(int)vc.size();i++)
		if((int)tp[i].size()>1)
		{
			int sz=(int)tp[i].size()-1;
			for(int j=0;j<=sz;j++)
				pre[j]=++nc,suf[j]=++nc;
			add_edge(pre[0],tp[i][0].sec),
			add_edge(suf[sz],tp[i][sz].sec);
			for(int j=1;j<=sz;j++)
				add_edge(pre[j],pre[j-1]),
				add_edge(pre[j],tp[i][j].sec);
			for(int j=sz-1;j>=0;j--)
				add_edge(suf[j],suf[j+1]),
				add_edge(suf[j],tp[i][j].sec);
			add_edge(tp[i][0].fir,suf[1]),
			add_edge(tp[i][sz].fir,pre[sz-1]);
			for(int j=1;j<sz;j++)
				add_edge(tp[i][j].fir,pre[j-1]),
				add_edge(tp[i][j].fir,suf[j+1]);
		}
//	cerr ln;
//	debug(vc.size())ln;
	build(rt,1,(int)vc.size());
//	cerr ln;
	for(int i=1;i<=n;i++)
		add_edge(lfid[x[i]],Q[i]),
		add_edge(lfid[y[i]],P[i]);
//	cerr ln;
	memcpy(hs,h,sizeof(int)*(nc+1)),etops=etop;
	int L=1,R=INF,mid=(L+R)>>1;
	while(L<=R)
	{
		if(check(n,mid)) L=mid+1;
		else R=mid-1;mid=(L+R)>>1;
	}
	return !printf("%d\n",R);
}

Measured memory_bytes: 52096