#include <bits/stdc++.h>
using namespace std;
int global_ans;
int n;
vector<vector<int>> graph;
vector<int> parent_arr;
vector<vector<int>> children_arr;
vector<int> size_arr;
vector<set<int>> res_sets;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
graph.resize(n+1);
for (int i = 0; i < n-1; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
parent_arr.assign(n+1, -1);
children_arr.resize(n+1);
vector<int> order;
queue<int> q;
q.push(1);
parent_arr[1] = -1;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : graph[u]) {
if (v == parent_arr[u]) continue;
parent_arr[v] = u;
children_arr[u].push_back(v);
q.push(v);
}
}
reverse(order.begin(), order.end());
size_arr.assign(n+1, 0);
res_sets.resize(n+1);
global_ans = 1e9;
for (int u : order) {
size_arr[u] = 1;
vector<set<int>> branch_sets;
for (int v : children_arr[u]) {
size_arr[u] += size_arr[v];
set<int> branch_set = res_sets[v];
branch_set.insert(size_arr[v]);
branch_sets.push_back(branch_set);
}
set<int> G;
if (branch_sets.size() >= 2) {
sort(branch_sets.begin(), branch_sets.end(), [](const set<int>& a, const set<int>& b) {
return a.size() < b.size();
});
for (auto &bs : branch_sets) {
for (int a : bs) {
if (!G.empty()) {
int total_rest = n - a;
double target_val = total_rest / 2.0;
auto it = G.lower_bound(target_val);
if (it != G.end()) {
int b = *it;
int s1 = a;
int s2 = b;
int s3 = n - a - b;
int max_val = max({s1, s2, s3});
int min_val = min({s1, s2, s3});
int gap = max_val - min_val;
if (gap < global_ans) global_ans = gap;
}
if (it != G.begin()) {
auto it_prev = prev(it);
int b = *it_prev;
int s1 = a;
int s2 = b;
int s3 = n - a - b;
int max_val = max({s1, s2, s3});
int min_val = min({s1, s2, s3});
int gap = max_val - min_val;
if (gap < global_ans) global_ans = gap;
}
}
}
for (int a : bs) {
G.insert(a);
}
}
} else if (branch_sets.size() == 1) {
G = branch_sets[0];
}
if (parent_arr[u] != -1) {
int T = size_arr[u];
int x = n - T;
vector<double> targets = { (double)n/3, (double)T - (double)n/3, (double)T/2 };
for (double target_val : targets) {
auto it = G.lower_bound(target_val);
if (it != G.end()) {
int a = *it;
int max_val = max({x, a, T - a});
int min_val = min({x, a, T - a});
int gap = max_val - min_val;
if (gap < global_ans) global_ans = gap;
}
if (it != G.begin()) {
auto it_prev = prev(it);
int a = *it_prev;
int max_val = max({x, a, T - a});
int min_val = min({x, a, T - a});
int gap = max_val - min_val;
if (gap < global_ans) global_ans = gap;
}
}
}
res_sets[u] = move(G);
}
cout << global_ans << endl;
return 0;
}
