#include<bits/stdc++.h>
using namespace std;
const int N=2e5+11;
typedef pair<int,int> PII;
struct q{
    int x,y,num;
}a[N],c[8];

struct w{
    int x,y,num;
}b[N];
int st[8],number[200];
unordered_map<int,int>m;
bool cmp1( q a, q b)
{
    return a.x<b.x;
}
bool cmp2( w a, w b)
{
    return a.y<b.y;
}
int main()
{
    int n;
    cin>>n;
    int i,j;
    for(i=0;i<n;i++)
    {
        int x1,y1;
        scanf("%d%d",&x1,&y1);
        a[i].x=b[i].x=x1;
        a[i].y=b[i].y=y1;
        a[i].num=b[i].num=i;
    }
    sort(a,a+n,cmp1);
    sort(b,b+n,cmp2);
    c[0]=a[0];
    c[1]=a[1];
    c[2]=a[n-2];
    c[3]=a[n-1];
    c[4]={b[0].x,b[0].y,b[0].num};
    c[5]={b[1].x,b[1].y,b[1].num};
    c[6]={b[n-2].x,b[n-2].y,b[n-2].num};
    c[7]={b[n-1].x,b[n-1].y,b[n-1].num};
    int idx=0,pos=0;
    
    //   for(i=0;i<8;i++)
    // {
    //     printf("%d %d\n",c[i].x,c[i].y);
    // }
    
    for(i=0;i<8;i++)
    {
        if(m.count(c[i].num)>=1)st[i]++;
        m[c[i].num]++;
    }
    
    for(i=0;i<8;i++)
    {
        if(st[i])idx++;
        else c[pos++]=c[i];
    }

    idx=8-idx;
    pos=0;
    sort(c,c+idx,cmp1);
    
    for(i=0;i<idx;i++)
    {
       for(j=i+1;j<idx;j++)
       {
           number[pos++]=max(abs(c[i].x-c[j].x),abs(c[i].y-c[j].y));
       }
    }
    // for(i=0;i<idx;i++)
    // {
    //     printf("%d %d\n",c[i].x,c[i].y);
    // }

    
    sort(number,number+pos);
    // for(i=0;i<pos;i++)
    // {
    //     printf("%d \n",number[i]);
    // }
    
    cout<<number[pos-2];
    return 0;
}
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#include<set>
#include <array>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define con continue
#define ub upper_bound
#define lb lower_bound

#define si(x) int(x.size())
#define sum_all(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
const double pi = 2 * acos(0.0);
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, -1, 0, 1 };

const int dx8[] = { -1, 0, 1, 0,1,1,-1,-1 };
const int dy8[] = { 0, -1, 0, 1,1,-1,1,-1 };

ll min(ll a,ll b)
{
    if(a<b)return a;
    return b; 
}
ll max(ll a,ll b)
{
    if(a>b)return a;
    return b; 
}
ll ceil1(ll a,ll b)
{
    return(a+b-1)/b;
}
void read(vector<ll> & arr)
{
  for(ll i=0;i<si(arr);i++)
    cin >> arr[i];

}

void read_graph(vector<vector<ll>>& g, ll m)
{
  while(m--)
  {
    ll x,y; cin >> x>> y ;
    x--,y--; 
    g[x].pb(y);
    g[y].pb(x);
  }
}
int lim=1e5 +13; 
vector<bool> col;
vector<int> c; 
vector<vector<int>> g; 
int cnt; 
vector<int> ans; 
void dfs(int r,int p=-1)
{

   for(auto a:g[r])
   {
     if(a==p) 
      continue; 
     if(!col[c[a]]) 
     {
      cnt++;
      ans.pb(a);
     }
     bool old= col[c[a]];
     col[c[a]]=true;
     dfs(a,r);
     col[c[a]]=old; 
   }
}
void solve()
{
 int n ;
 cin >> n; 
 c=vector<int>(n);
 g=vector<vector<int>>(n);
 for(int i=0;i<n;i++) cin >> c[i];
  for(int i=0;i<n-1;i++)
  {
     int x,y;
     cin >>x >> y ;
     x--,y--;
     g[x].pb(y);
     g[y].pb(x);
  }

 
col=vector<bool>(lim,false);
col[c[0]]=true;
cnt=0;
ans.clear(); 
ans.pb(0);
dfs(0);
sort(ans.begin(),ans.end());
for(int i=0;i<si(ans);i++) cout << 1+ans[i] << endl; 
// cout << cnt << endl; 
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    //int t; cin >> t; while (t--)
    solve();

}
