#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define rep(i, n) for (int i = 0; i < n; i++) #define per(i, n) for (int i = n - 1; i >= 0; i--) #define Rep(i, sta, n) for (int i = sta; i < n; i++) #define Per(i, sta, n) for (int i = n - 1; i >= sta; i--) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1}; int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1}; template using max_heap = priority_queue; template using min_heap = priority_queue, greater<>>; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } struct edge { int to, id, t; edge() {} edge(int to, int id, int t) : to(to), id(id), t(t) {} }; int n; vector G[200010]; int depth[200010], di[200010][2]; P max_depth[200010][3]; void dfs1(int s, int par, edge pre_e) { if (par != -1) depth[s] = depth[par] + 1; for (edge e : G[s]) { if (e.to == par) continue; dfs1(e.to, s, e); if (max_depth[s][0].first < max_depth[e.to][2].first + 1) { max_depth[s][0] = {max_depth[e.to][2].first + 1, e.id}; sort(max_depth[s], max_depth[s] + 3); } if (pre_e.id != -1) chmax(di[pre_e.id][pre_e.t], di[e.id][e.t]); } if (pre_e.id != -1) chmax(di[pre_e.id][pre_e.t], max_depth[s][2].first + max_depth[s][1].first); } void dfs2(int s, int par, edge pre_e, int depth_par) { set

v = {max_depth[s][0], max_depth[s][1], max_depth[s][2], P(depth_par, pre_e.id)}; for (edge e : G[s]) { if (e.to == par) continue; P erased = P(-1, -1); for (P p : v) if (p.second == e.id) { erased = p; v.erase(p); } auto it = v.end(); it--; int d_first = (*it).first; it--; int d_second = (*it).first; dfs2(e.to, s, e, d_first + 1); chmax(di[e.id][1 - e.t], d_first + d_second); if (erased != P(-1, -1)) v.insert(erased); } } void dfs3(int s, int par, edge pre_e) { for (edge e : G[s]) { if (e.to == par) continue; if (par != -1) chmax(di[e.id][1 - e.t], di[pre_e.id][1 - pre_e.t]); dfs3(e.to, s, e); } } void solve() { cin >> n; rep(i, n - 1) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(edge(b, i, 0)); G[b].push_back(edge(a, i, 1)); } rep(i, n) rep(j, 3) max_depth[i][j] = P(0, -1); rep(i, n - 1) rep(j, 2) di[i][j] = -1; dfs1(0, -1, edge(0, -1, -1)); // rep(i, n) cout << depth[i] << " "; // cout << "" << endl; // rep(i, n) { // rep(j, 3) cout << max_depth[i][j].first << " "; // cout << "" << endl; // } dfs2(0, -1, edge(0, -1, -1), 0); // dfs3(0, -1, edge(0, -1, -1)); // // rep(i, n - 1) { cout << di[i][0] << " " << di[i][1] << endl; } // int ans = mod; // rep(i, n - 1) { chmin(ans, 1 + (di[i][0] + 1) / 2 + (di[i][1] + 1) / 2); } // cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }