#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define M n*2
#define f(x,y) (x+y*n)
#define N 10011
#define MAXN 500011
using namespace std;
struct apple{
	int v,nxt;
}edge[MAXN*10];
struct node{
	int lson,rson;
}tree[MAXN];
int indexx[MAXN],tot,a[N][2],col[MAXN],vist[MAXN],dfn[MAXN],low[MAXN],n,root,ans,maxx,siz,que[MAXN],top,a1[MAXN],a2[MAXN];
int ti,c;
stack<int> Stack;
vector<int> V[MAXN];
void addedge(int x,int y){
	edge[++tot].v=y;
	edge[tot].nxt=indexx[x];
	indexx[x]=tot;
//	printf("%d %d\n",x,y);
}
void add(int &now,int k,int p,int x,int l,int r){
	if(!now){
		now=++siz;
		memset(&tree[now],0,sizeof(tree[now]));
		V[now].clear();
		if(l==r) que[++top]=now;
		if(k) addedge(k+M,now+M);
	}
	if(l==r){
		addedge(now+M,x);
//		int len=V[now].size();
//		for(int i=0;i<len;i++){
//			addedge(x>n ? x-n :x+n,V[now][i]);
//			addedge(V[now][i]>n ? V[now][i]-n : V[now][i]+n,x);
//		}
		V[now].push_back(x);
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid) add(tree[now].lson,now,p,x,l,mid);
	else add(tree[now].rson,now,p,x,mid+1,r);
}
void Add(int now,int x,int ql,int qr,int ban,int l,int r){
	if(!now) return;
	if(ql<=l && r<=qr){
		addedge(x,now+M);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid) Add(tree[now].lson,x,ql,qr,ban,l,mid);
	if(qr>mid) Add(tree[now].rson,x,ql,qr,ban,mid+1,r);
}
void dfs(int u){
	Stack.push(u);
	vist[u]=1;
	dfn[u]=low[u]=++ti;
	int t=indexx[u],vv;
	while(t){
		vv=edge[t].v;
		if(!dfn[vv]){
			dfs(vv);
			low[u]=min(low[u],low[vv]);
		}
		else if(vist[vv]) low[u]=min(low[u],dfn[vv]);
		t=edge[t].nxt;
	}
	if(dfn[u]==low[u]){
		int x=Stack.top();
		Stack.pop();
		col[x]=++c;
		vist[x]=0;
		while(x!=u){
			x=Stack.top();
			Stack.pop();
			col[x]=c;
			vist[x]=0;
		}
	}
}
int judge(int avr){
//	printf("\n\n\n%d\n",avr);
	memset(indexx,0,sizeof(indexx));
	memset(col,0,sizeof(col));c=siz=0;
	memset(dfn,0,sizeof(dfn));ti=0;
	memset(low,0,sizeof(low));tot=0;
	root=0;top=0;
	for(int i=1;i<=n;i++){
		add(root,0,a[i][0],f(i,1),0,maxx);
		add(root,0,a[i][1],f(i,0),0,maxx);
	}
	int num=siz+M;
	for(int i=1;i<=top;i++){
		int now=que[i];
		int len=V[now].size();
		for(int j=0;j<len;j++){
			a1[j]=++num;
			a2[j]=++num;
			addedge(a1[j],V[now][j]);
			addedge(a2[j],V[now][j]);
			if(j){
				addedge(a1[j-1],a1[j]);
				addedge(a2[j],a2[j-1]);
			}
		}
		for(int j=0;j<len;j++){
			if(j<len-1) addedge(V[now][j]>n ? V[now][j]-n : V[now][j]+n,a1[j+1]);
			if(j) addedge(V[now][j]>n ? V[now][j]-n : V[now][j]+n,a2[j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		Add(root,f(i,0),max(0,a[i][0]-avr+1),a[i][0]-1,0,0,maxx);
		Add(root,f(i,0),a[i][0]+1,min(a[i][0]+avr-1,maxx),0,0,maxx);
//		Add(root,f(i,0),max(0,a[i][0]-avr+1),min(a[i][0]+avr-1,maxx),0,0,maxx);
		
		Add(root,f(i,1),max(0,a[i][1]-avr+1),a[i][1]-1,0,0,maxx);
		Add(root,f(i,1),a[i][1]+1,min(a[i][1]+avr-1,maxx),0,0,maxx);
	}
	for(int i=1;i<=2*n;i++){
		if(!dfn[i]) dfs(i);
	}
	for(int i=1;i<=n;i++){
		if(col[f(i,0)]==col[f(i,1)]) return 0;
	}
	return 1;
}
void bin(){
	int head=0,tail=maxx,mid;
	while(head<=tail){
		mid=(head+tail)/2;
		if(judge(mid)){
			head=mid+1;
			ans=mid;
		}
		else tail=mid-1;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i][0],&a[i][1]);
		maxx=max(maxx,a[i][0]);
		maxx=max(maxx,a[i][1]);
	}
	bin();
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 52740