#include #define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1)) using namespace std; using ll = long long; using pii = pair; constexpr int MOD = int(1e9 + 7); constexpr int INF = int(1e9 + 1); constexpr ll LLINF = ll(4 * 1e18 + 1); // constexpr int INF = 2147483647; // 2 * 1e9 // constexpr ll LLINF = 9223372036854775807; // 9 * 1e18 const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; struct Edge{ int to; int cost; }; vector g[100000]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); int n; cin >> n; for(int i = 0; i < n - 1; ++i){ int a, b; cin >> a >> b; --a; --b; g[a].push_back({b, 1}); g[b].push_back({a, 1}); } priority_queue, vector>, greater>> que; vector d(n, INF); d[0] = 0; que.push({int(0), 0}); while(!que.empty()){ int c = que.top().first; int v = que.top().second; que.pop(); for(auto && e : g[v]){ if(d[e.to] > c + e.cost){ d[e.to] = c + e.cost; que.push({d[e.to], e.to}); } } } int ma = -1, mai = -1; for(int i = 0; i < n; ++i){ if(ma < d[i]){ ma = d[i]; mai = i; } } priority_queue, vector>, greater>> que2; vector d2(n, INF); d2[mai] = 0; que2.push({int(0), mai}); while(!que2.empty()){ int c = que2.top().first; int v = que2.top().second; que2.pop(); for(auto && e : g[v]){ if(d2[e.to] > c + e.cost){ d2[e.to] = c + e.cost; que2.push({d2[e.to], e.to}); } } } int ma2 = 0; for(int i = 0; i < n; ++i){ ma2 = max(ma2, d2[i]); } cout << n - ma2 - 1 << "\n"; return 0; }