#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int INF = 1e9;
int n;
vector<vi> adj;
vi tin, tout, sz, euler;
int timer;
vector<vi> st; // segment tree: mỗi node giữ vector đã sort
// DFS tính tin/tout và sz[u]
void dfs(int u, int p){
tin[u] = ++timer;
euler[timer] = u;
sz[u] = 1;
for(int v : adj[u]) if(v != p){
dfs(v, u);
sz[u] += sz[v];
}
tout[u] = timer;
}
// Xây segment-tree trên mảng A[i] = sz[euler[i]]
void build(int node, int l, int r){
if(l == r){
st[node] = vi(1, sz[euler[l]]);
} else {
int m = (l + r) >> 1;
build(node<<1, l, m);
build(node<<1|1, m+1, r);
st[node].resize(st[node<<1].size() + st[node<<1|1].size());
merge(st[node<<1].begin(), st[node<<1].end(),
st[node<<1|1].begin(), st[node<<1|1].end(),
st[node].begin());
}
}
// Tìm predecessor = max{x ≤ target} trong đoạn [L,R], hoặc -INF nếu không có
int queryPred(int node, int l, int r, int L, int R, int target){
if(R < l || r < L) return -INF;
if(L <= l && r <= R){
auto &v = st[node];
auto it = upper_bound(v.begin(), v.end(), target);
if(it == v.begin()) return -INF;
--it;
return *it;
}
int m = (l + r) >> 1;
return max(
queryPred(node<<1, l, m, L, R, target),
queryPred(node<<1|1, m+1, r, L, R, target)
);
}
// Tìm successor = min{x ≥ target} trong đoạn [L,R], hoặc +INF nếu không có
int querySucc(int node, int l, int r, int L, int R, int target){
if(R < l || r < L) return +INF;
if(L <= l && r <= R){
auto &v = st[node];
auto it = lower_bound(v.begin(), v.end(), target);
if(it == v.end()) return +INF;
return *it;
}
int m = (l + r) >> 1;
return min(
querySucc(node<<1, l, m, L, R, target),
querySucc(node<<1|1, m+1, r, L, R, target)
);
}
// Truy vấn trong [L,R] cả pred & succ gần target
void queryClosest(int L, int R, int target, vector<int>& out){
if(L > R) return;
int p = queryPred(1,1,n,L,R,target);
int s = querySucc(1,1,n,L,R,target);
if(p != -INF) out.push_back(p);
if(s != +INF) out.push_back(s);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
adj.assign(n+1, {});
for(int i=0;i<n-1;i++){
int x,y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
tin.assign(n+1,0);
tout.assign(n+1,0);
sz.assign(n+1,0);
euler.assign(n+1,0);
timer = 0;
dfs(1,0);
// khởi tạo segment-tree
st.assign(4*(n+2), vi());
build(1,1,n);
int answer = n; // khởi gán lớn
// duyệt từng u làm vị trí cắt thứ nhất
for(int u = 1; u <= n; u++){
int su = sz[u];
int R = n - su;
// ----- CASE A: nested (cắt thứ hai trong subtree của u) -----
if(tin[u]+1 <= tout[u]){
vector<int> cands;
int target = su / 2;
queryClosest(tin[u]+1, tout[u], target, cands);
for(int sv : cands){
int a = sv;
int b = su - sv;
int c = R;
int mx = max({a,b,c});
int mn = min({a,b,c});
answer = min(answer, mx - mn);
}
}
// ----- CASE B: disjoint (cắt thứ hai ngoài subtree) -----
if(R > 0){
vector<int> cands;
int target = R / 2;
// hai khoảng [1, tin[u]-1] và [tout[u]+1, n]
if(1 <= tin[u]-1)
queryClosest(1, tin[u]-1, target, cands);
if(tout[u]+1 <= n)
queryClosest(tout[u]+1, n, target, cands);
for(int sv : cands){
int a = su;
int b = sv;
int c = R - sv;
int mx = max({a,b,c});
int mn = min({a,b,c});
answer = min(answer, mx - mn);
}
}
}
cout << answer << "\n";
return 0;
}
