#include <cstdio>
#include <vector>

constexpr int maxn = 2e5+10;

std::vector<int> g[maxn];

int dist[maxn], color[maxn], t = 1, l, r;
bool has[maxn];

void dfs(int u, int p = 0) {
	for(int v : g[u]) {
		if(v == p) continue;
		dist[v] = dist[u] + 1;
		dfs(v, u);
	}
}

void pre(int u, int p = 0) {
	has[u] = u == r;
	for(int& v : g[u]) {
		if(v != p) {
			pre(v, u);
			has[u] |= has[v];
			if(has[v]) std::swap(v, g[u][0]);
		}
	}
	if(g[u].size() && has[u]) std::swap(g[u][0], g[u].back());
}

void get(int u, int p = 0) {
	color[u] = t++;
	for(int v : g[u])
		if(v != p) get(v, u), t++;
}

int main() {
	int n; scanf("%d", &n);
	for(int i = 1, a, b; i < n; i++)
		scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
	dfs(1);
	l = 1, r = 1;
	for(int i = 1; i <= n; i++)
		if(dist[i] > dist[l]) l = i;
	dist[l] = 0;
	dfs(l);
	for(int i = 1; i <= n; i++)
		if(dist[i] > dist[r]) r = i;
	pre(l);
	get(l);
	for(int i = 1; i <= n; i++)
		printf("%d%c", color[i], " \n"[i==n]);
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct point {
    int x, y, ind;
};
bool comp(point a, point b) {
    return a.x < b.x;
}
void solve() {
    int n; cin >> n;
    vector<point> a(n), b(n);
    for (int i = 0 ; i < n; ++i) {
        cin >> a[i].x >> a[i].y;
        b[i].x = a[i].y; b[i].y = a[i].x;
        a[i].ind = i;
        b[i].ind = i;
    }
    sort(a.begin(), a.end(), comp);
    sort(b.begin(), b.end(), comp);
    vector<pair<int, pair<int, int> > > dist;
    for (int i = 0; i < 2; ++i) {
        for (int j = n - 1; j >= n - 2; --j) {
            int d1 = abs(a[i].x - a[j].x), d2 = abs(b[i].x - b[j].x);
            int ind1 =  a[i].ind, ind2 = a[j].ind, ind3 = b[i].ind, ind4 = b[j].ind;
            if (ind1 > ind2) swap(ind1, ind2);
            if (ind3 > ind4) swap(ind3, ind4);
            dist.push_back({d1, {ind1, ind2}});
            dist.push_back({d2, {ind3, ind4}});
        }
    }
    sort(dist.begin(), dist.end());
    int m = dist.size();
    if (dist[m - 1].second.first == dist[m - 2].second.first && dist[m - 1].second.second == dist[m - 2].second.second ) {
        cout << dist[m - 3].first << endl;
    }
    else cout << dist[m - 2].first << endl;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("input1.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i)
    {
        solve();
    }
}