#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const int MAXN = 200000;
int n;
vector<int> adj[MAXN+1], children[MAXN+1];
int parentArr[MAXN+1], sz[MAXN+1];
int stk[MAXN+1], ord[MAXN+1], ordsz;
// 1) Tính sz[u] cho mỗi u bằng DFS không đệ quy
void build_tree() {
ordsz = 0;
int top = 0;
stk[top++] = 1;
parentArr[1] = 0;
while (top) {
int u = stk[--top];
ord[ordsz++] = u;
for (int v : adj[u]) {
if (v == parentArr[u]) continue;
parentArr[v] = u;
children[u].push_back(v);
stk[top++] = v;
}
}
for (int i = ordsz - 1; i >= 0; --i) {
int u = ord[i];
sz[u] = 1;
for (int v : children[u]) {
sz[u] += sz[v];
}
}
}
ll best;
// Phần DISJOINT-CASE: lấy global list allSz, tìm cặp gần 2n/3
void solve_disjoint() {
vector<int> allSz;
allSz.reserve(n-1);
for (int u = 2; u <= n; ++u) {
allSz.push_back(sz[u]);
}
sort(allSz.begin(), allSz.end());
// two-pointer + binary-search quanh mục tiêu
for (int i = 0; i < (int)allSz.size(); ++i) {
ll a = allSz[i];
ll target = (2LL*n)/3 - a;
// tìm lower_bound bên phải i
int lo = i+1, hi = allSz.size()-1, pos = allSz.size();
while (lo <= hi) {
int mid = (lo+hi)/2;
if (allSz[mid] >= target) {
pos = mid;
hi = mid-1;
} else lo = mid+1;
}
for (int j = max(i+1, pos-2); j <= min((int)allSz.size()-1, pos+2); ++j) {
if (j <= i) continue;
ll b = allSz[j];
ll c = n - a - b;
ll mn = min(a, min(b, c));
ll mx = max(a, max(b, c));
best = min(best, mx - mn);
}
}
}
// Phần ANCESTOR-CASE: small-to-large merge multiset
set<int>* ms[MAXN+1];
void dfs_small_to_large(int u) {
// bắt đầu: ms[u] có chứa chính sz[u]? Không, chỉ lưu các sz[f] của edges bên dưới u
ms[u] = new set<int>();
for (int v : children[u]) {
dfs_small_to_large(v);
// merge nhỏ->lớn: ensure ms[u] là lớn nhất
if (ms[v]->size() > ms[u]->size())
swap(ms[v], ms[u]);
// gộp tất cả phần tử của ms[v] vào ms[u]
for (int x : *ms[v])
ms[u]->insert(x);
delete ms[v];
}
// bây giờ chèn cả chính cây con (u->parent) vào: tức kích thước của edge parent–u
if (u != 1)
ms[u]->insert(sz[u]);
// nếu u có parent, thì xem xét cắt (parent–u) và một cạnh bên trong subtree(u):
if (u != 1) {
ll S = sz[u], other = n - S;
// ta muốn pick a trong ms[u] sao cho a ≈ S/2 để chia S thành (a, S-a)
auto it = ms[u]->lower_bound(S/2);
for (int rep = 0; rep < 2; ++rep) {
if (it == ms[u]->end()) {
if (it == ms[u]->begin()) break;
--it;
}
ll a = *it;
ll b = S - a;
ll c = other;
ll mn = min(a, min(b, c));
ll mx = max(a, max(b, c));
best = min(best, mx - mn);
if (it == ms[u]->begin()) break;
--it;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; ++i) {
adj[i].clear();
children[i].clear();
}
for (int i = 1; i < n; ++i) {
int x,y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
build_tree();
best = LLONG_MAX;
solve_disjoint();
dfs_small_to_large(1);
cout << best << "\n";
return 0;
}
