#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<vector<int>> g;
vector<int> sz;
// 1) DFS tính sz[u]
void dfs_sz(int u, int p) {
sz[u] = 1;
for (int v : g[u]) if (v != p) {
dfs_sz(v, u);
sz[u] += sz[v];
}
}
// 2) Tìm một centroid, bắt đầu từ u
int find_centroid(int u, int p) {
for (int v : g[u]) if (v != p) {
if (sz[v] > n/2)
return find_centroid(v, u);
}
return u;
}
// 3) Từ một centroid C, lấy tất cả sizes của các cây con kề C
vector<int> get_neighbor_sizes(int C) {
vector<int> S;
for (int v : g[C]) {
// nếu v nằm “phía trên” C thì kích thước là n - sz[C]
// ngược lại là sz[v]
if (sz[v] < sz[C]) S.push_back(sz[v]);
else S.push_back(n - sz[C]);
}
return S;
}
// 4) Tính hiệu gap tốt nhất trong mảng S
int best_gap_from_sizes(vector<int>& S) {
int m = S.size();
if (m < 2) return INT_MAX;
sort(S.begin(), S.end());
int best = INT_MAX;
// hai con trỏ
int i = 0, j = m-1;
// chúng ta muốn hai giá trị a=S[i], b=S[j] sao cho max(a,b,n-a-b)-min(...) nhỏ nhất
// nhưng vì m thường rất nhỏ, đơn giản thử mọi cặp i<j
for (int x = 0; x < m; x++) {
for (int y = x+1; y < m; y++) {
ll a = S[x], b = S[y], c = ll(n) - a - b;
ll mx = max(a, max(b, c));
ll mn = min(a, min(b, c));
best = min(best, int(mx - mn));
}
}
return best;
}
int solve_single_centroid(int C) {
// đảm bảo sz[] đã đúng với toàn cây, và C là centroid
auto S = get_neighbor_sizes(C);
return best_gap_from_sizes(S);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
g.assign(n+1, {});
for (int i = 0,u,v; i < n-1; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
sz.assign(n+1, 0);
dfs_sz(1, 0);
int C1 = find_centroid(1, 0);
// Recompute sz từ C1 để chuẩn cho phần "n - sz[C1]" nếu cần
dfs_sz(C1, 0);
int ans = solve_single_centroid(C1);
// Kiểm tra có thể có 2 centroid không?
int C2 = -1;
for (int v : g[C1]) {
if (sz[v] > n/2) {
C2 = find_centroid(v, C1);
break;
}
}
if (C2 != -1 && C2 != C1) {
// Tái dfs để sz[] đúng với root = C2
dfs_sz(C2, 0);
ans = min(ans, solve_single_centroid(C2));
}
cout << ans << "\n";
return 0;
}
