#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int INF = 1e9;
int n;
vector<vi> adj, children;
vi tin, tout, euler, sz, B;
int timer;
int ans;
// --- 1) DFS1: Euler tour + tính sz[u] ---
void dfs1(int u, int p){
tin[u] = ++timer;
euler[timer] = u;
sz[u] = 1;
for(int v: adj[u]){
if(v == p) continue;
children[u].push_back(v);
dfs1(v, u);
sz[u] += sz[v];
}
tout[u] = timer;
}
// bests[u] sẽ chứa 1–2 ứng viên a' cho case disjoint của u
vector<vector<int>> bests;
// --- 2) Forward scan cho prefix [1..tin[u]-1], loại trừ root ---
void forward_scan(){
multiset<int> st;
vector<vector<int>> atTin(n+1);
for(int u = 2; u <= n; u++)
atTin[tin[u]].push_back(u);
for(int i = 1; i <= n; i++){
// xử lý disjoint-prefix cho mọi u với tin[u] == i
for(int u: atTin[i]){
int r = n - sz[u];
int target = r / 2;
if(!st.empty()){
auto it = st.lower_bound(target);
if(it != st.end()) bests[u].push_back(*it);
if(it != st.begin()){
--it;
bests[u].push_back(*it);
}
}
}
// chèn B[i] = sz[euler[i]] nếu euler[i] != 1
if(euler[i] != 1)
st.insert(B[i]);
}
}
// --- 3) Backward scan cho suffix [tout[u]+1..n], loại trừ root ---
void backward_scan(){
multiset<int> st;
vector<vector<int>> atTout(n+2);
for(int u = 2; u <= n; u++)
atTout[tout[u]].push_back(u);
for(int i = n; i >= 1; i--){
for(int u: atTout[i]){
int r = n - sz[u];
int target = r / 2;
if(!st.empty()){
auto it = st.lower_bound(target);
if(it != st.end()) bests[u].push_back(*it);
if(it != st.begin()){
--it;
bests[u].push_back(*it);
}
}
}
if(euler[i] != 1)
st.insert(B[i]);
}
}
// --- 4) DSU-on-Tree để tìm case nested và kết hợp disjoint từ bests[u] ---
set<int>* dfs_dsu(int u){
// S chứa sz[x] cho tất cả x trong subtree(u), x != u
auto *S = new set<int>();
for(int v: children[u]){
auto *Sv = dfs_dsu(v);
if(S->size() < Sv->size()) swap(S, Sv);
// merge Sv vào S
for(int x: *Sv)
S->insert(x);
delete Sv;
}
// --- case nested: tìm a trong S sao cho a ≈ sz[u]/2 ---
if(!S->empty()){
int s = sz[u], r = n - s;
int target = s / 2;
auto it = S->lower_bound(target);
vector<int> cands;
if(it != S->end()) cands.push_back(*it);
if(it != S->begin()){
--it;
cands.push_back(*it);
}
for(int a: cands){
int b = s - a;
int mx = max({a,b,r});
int mn = min({a,b,r});
ans = min(ans, mx - mn);
}
}
// --- case disjoint: dùng bests[u] từ forward/backward ---
int s = sz[u];
for(int a: bests[u]){
int b = (n - s) - a;
int c = s;
int mx = max({a,b,c});
int mn = min({a,b,c});
ans = min(ans, mx - mn);
}
// thêm sz[u] vào S để các ancestor có thể dùng
S->insert(sz[u]);
return S;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
adj.assign(n+1, {});
children.assign(n+1, {});
tin.assign(n+1,0);
tout.assign(n+1,0);
euler.assign(n+1,0);
sz.assign(n+1,0);
B.assign(n+1,0);
bests.assign(n+1, {});
for(int i = 1, x, y; i < n; i++){
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
timer = 0;
dfs1(1, 0);
// xây B[i] = sz[euler[i]]
for(int i = 1; i <= n; i++)
B[i] = sz[euler[i]];
// thu disjoint‑candidates
forward_scan();
backward_scan();
ans = INF;
// DSU‑on‑Tree tổng hợp nested & disjoint
auto *rootSet = dfs_dsu(1);
delete rootSet;
cout << ans << "\n";
return 0;
}
