#include<bits/stdc++.h>

using namespace std;

struct StronglyConnectedComponents
{
  vector< vector< int > > gg, rg;
  vector< pair< int, int > > edges;
  vector< int > comp, order, used;

  StronglyConnectedComponents(size_t v) : gg(v), rg(v), comp(v, -1), used(v, 0) {}

  virtual void add_edge(int x, int y)
  {
    gg[x].push_back(y);
    rg[y].push_back(x);
    edges.emplace_back(x, y);
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  void dfs(int idx)
  {
    if(used[idx]) return;
    used[idx] = true;
    for(int to : gg[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt)
  {
    if(comp[idx] != -1) return;
    comp[idx] = cnt;
    for(int to : rg[idx]) rdfs(to, cnt);
  }

  void build(vector< vector< int > > &t)
  {
    for(int i = 0; i < gg.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++;

    /*
    t.resize(ptr);
    set< pair< int, int > > connect;
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      if(connect.count({x, y})) continue;
      t[x].push_back(y);
      connect.emplace(x, y);
    }
     */
  }
};

struct TwoSatisfiability : StronglyConnectedComponents
{
  int sz;

  TwoSatisfiability(size_t v) : sz(v), StronglyConnectedComponents(v + v) {}

  void add_edge2(int u, int v)
  {
    StronglyConnectedComponents::add_edge(rev(u), v);
    StronglyConnectedComponents::add_edge(rev(v), u);
  }

  inline int rev(int x)
  {
    if(x >= sz) return (x - sz);
    return (x + sz);
  }

  bool operator()(int v)
  {
    return ((*this)[v] > (*this)[rev(v)]);
  }

  bool solve()
  {
    vector< vector< int > > g;
    build(g);
    for(int i = 0; i < sz; i++) {
      if((*this)[i] == (*this)[rev(i)]) return (false);
    }
    return (true);
  }
};

struct SegmentTree
{
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
  }

  void range(int a, int b, int k, int l, int r, const function< void(int) > &f)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      f(k);
      return;
    }
    range(a, b, 2 * k + 1, l, (l + r) >> 1, f);
    range(a, b, 2 * k + 2, (l + r) >> 1, r, f);
  }

  void range(int a, int b, const function< void(int) > &f)
  {
    range(a, b, 0, 0, sz, f);
  }
};

int main()
{
  int N, X[10000], Y[10000];

  scanf("%d", &N);

  vector< pair< int, int > > xs(N + N);
  for(int i = 0; i < N; i++) {
    scanf("%d %d", &X[i], &Y[i]);
    xs[i] = {X[i], i};
    xs[i + N] = {Y[i], i + N};
  }
  sort(begin(xs), end(xs));
  for(int i = 0; i < N; i++) {
    X[i] = lower_bound(begin(xs), end(xs), make_pair(X[i], i)) - begin(xs);
    Y[i] = lower_bound(begin(xs), end(xs), make_pair(Y[i], i + N)) - begin(xs);
  }

  SegmentTree seg(2 * N);

  auto check = [&](int dist)
  {
    TwoSatisfiability sat(2 * seg.sz - 1);
    for(int i = seg.sz - 2; i >= 0; i--) {
      sat.add_edge(2 * i + 1, i);
      sat.add_edge(2 * i + 2, i);
      sat.add_edge(sat.rev(2 * i + 1), sat.rev(i));
      sat.add_edge(sat.rev(2 * i + 2), sat.rev(i));
    }
    int left = 0, right = 0;
    for(int i = 0; i < 2 * N; i++) {
      while(xs[i].first - xs[left].first >= dist) ++left;
      while(right < 2 * N && xs[right].first - xs[i].first < dist) ++right;
      seg.range(left, i, [&](int k)
      {
        sat.add_edge2(sat.rev(i + seg.sz - 1), sat.rev(k));
      });
      seg.range(i + 1, right, [&](int k)
      {
        sat.add_edge2(sat.rev(i + seg.sz - 1), sat.rev(k));
      });
    }
    for(int i = 0; i < N; i++) {
      sat.add_edge2(X[i] + seg.sz - 1, Y[i] + seg.sz - 1);
    }
    return (sat.solve());
  };


  int correct = 0, ng = 1 << 30;
  while(ng - correct > 1) {
    int mid = (correct + ng) >> 1;
    if(check(mid)) correct = mid;
    else ng = mid;
  }

  printf("%d\n", correct);
}

Measured memory_bytes: 48872