อุโมงค์ตัวตุ่น: พอรู้ว่าจะปิดเส้นไหน ต่อที่ห้องกลางได้เสมอ

// ลองปิดทีละเส้น แต่ไม่ลองคู่ห้องแล้ว ต่อที่จุดกึ่งกลางของสองก้อนเสมอ
// งานราว 2N ต่อเส้น รวมราว 2N² ทันกับ N ไม่ถึง 3,000
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> g;
vector<int> d, pa, seen;

// เดินกว้างจาก s โดยห้ามข้ามเส้น (ba, bb) เก็บระยะ พ่อ และลำดับห้องที่ไปถึง
void bfs(int s, int ba, int bb){
    for(int v : seen) d[v] = -1;              // ล้างเฉพาะห้องของรอบก่อน
    seen.clear(); seen.push_back(s); d[s] = 0; pa[s] = 0;
    for(size_t i = 0; i < seen.size(); i++){ int u = seen[i];
        for(int v : g[u]){
            if((u == ba && v == bb) || (u == bb && v == ba)) continue;
            if(d[v] < 0){ d[v] = d[u] + 1; pa[v] = u; seen.push_back(v); } } }
}

// เดินกว้างสองรอบ ได้ความยาวของก้อนที่ s อยู่ กับห้องกึ่งกลางของมัน
pair<int,int> diamCenter(int s, int ba, int bb){
    bfs(s, ba, bb);
    int u = s; for(int x : seen) if(d[x] > d[u]) u = x;
    bfs(u, ba, bb);
    int w = u; for(int x : seen) if(d[x] > d[w]) w = x;
    int len = d[w], cur = w;
    for(int k = 0; k < len / 2; k++) cur = pa[cur];   // ถอยกลับครึ่งทาง
    return {len, cur};
}

int main(){
    if(scanf("%d", &N) != 1) return 0;
    g.assign(N + 1, {}); d.assign(N + 1, -1); pa.assign(N + 1, 0);
    vector<pair<int,int>> E(N - 1);
    for(auto &e : E){ if(scanf("%d %d", &e.first, &e.second) != 2) return 0;
        g[e.first].push_back(e.second); g[e.second].push_back(e.first); }
    if(N == 1){ printf("0\n"); return 0; }

    int best = INT_MAX; int bi = 0, bx = 0, by = 0;
    for(int i = 0; i < N - 1; i++){
        auto [a, b] = E[i];
        auto [d1, c1] = diamCenter(a, a, b);
        auto [d2, c2] = diamCenter(b, a, b);
        int s = max(max(d1, d2), (d1 + 1) / 2 + (d2 + 1) / 2 + 1);
        if(s < best){ best = s; bi = i; bx = c1; by = c2; } }
    printf("%d\n%d %d\n%d %d\n", best, E[bi].first, E[bi].second, bx, by);
}

#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> head_, nxt_, to_;
void addEdge(int u, int v){ to_.push_back(v); nxt_.push_back(head_[u]); head_[u] = (int)to_.size() - 1; }
vector<int> par, ord_, h, dd, uh, ud;

// เดินจาก s ในกราฟที่ตัดเส้น (ba, bb) ออกแล้ว คืนระยะทางกับพ่อของทุกปมที่ไปถึง
void bfs(int s, int ba, int bb, vector<int>&d, vector<int>&pa, vector<int>&seen){
    d[s] = 0; pa[s] = 0; seen.clear(); seen.push_back(s);
    for(size_t i = 0; i < seen.size(); i++){ int u = seen[i];
        for(int e = head_[u]; e != -1; e = nxt_[e]){ int v = to_[e];
            if((u == ba && v == bb) || (u == bb && v == ba)) continue;
            if(d[v] < 0){ d[v] = d[u] + 1; pa[v] = u; seen.push_back(v); } } }
}

int main(){
    if(scanf("%d", &N) != 1) return 0;
    head_.assign(N + 1, -1);
    for(int i = 0; i < N - 1; i++){ int a, b; scanf("%d %d", &a, &b); addEdge(a, b); addEdge(b, a); }
    if(N == 1){ printf("0\n"); return 0; }              // ไม่มีอุโมงค์ให้ปิด

    par.assign(N + 1, 0); ord_.reserve(N);
    h.assign(N + 1, 0); dd.assign(N + 1, 0); uh.assign(N + 1, 0); ud.assign(N + 1, 0);
    // เรียงแบบกว้างก่อนแล้วไล่ย้อน แทนการเรียกซ้ำ ต้นไม้สูงสามแสนชั้นจึงไม่ทำสแต็กแตก
    vector<char> vis(N + 1, 0); ord_.push_back(1); vis[1] = 1;
    for(size_t i = 0; i < ord_.size(); i++){ int u = ord_[i];
        for(int e = head_[u]; e != -1; e = nxt_[e]){ int v = to_[e];
            if(!vis[v]){ vis[v] = 1; par[v] = u; ord_.push_back(v); } } }

    // ขาลง h = ความสูงของกิ่ง, dd = เส้นผ่านศูนย์กลางภายในกิ่ง
    for(int i = N - 1; i >= 0; i--){ int v = ord_[i]; int a1 = 0, a2 = 0;
        for(int e = head_[v]; e != -1; e = nxt_[e]){ int c = to_[e]; if(c == par[v]) continue;
            int a = h[c] + 1; if(a > a1){ a2 = a1; a1 = a; } else if(a > a2) a2 = a;
            dd[v] = max(dd[v], dd[c]); }
        h[v] = a1; dd[v] = max(dd[v], a1 + a2); }

    // ขาขึ้น uh = ระยะไกลสุดที่ออกไปทางพ่อ, ud = เส้นผ่านศูนย์กลางของส่วนที่เหลือ
    for(int i = 0; i < N; i++){ int p = ord_[i];
        int a1 = 0, a2 = 0, a3 = 0, i1 = -1, i2 = -1;     // สามอันดับของระยะลงไปในลูก
        int d1 = 0, d2 = 0, j1 = -1;                       // สองอันดับของเส้นผ่านศูนย์กลางในลูก
        for(int e = head_[p]; e != -1; e = nxt_[e]){ int c = to_[e]; if(c == par[p]) continue;
            int a = h[c] + 1;
            if(a > a1){ a3 = a2; a2 = a1; i2 = i1; a1 = a; i1 = c; }
            else if(a > a2){ a3 = a2; a2 = a; i2 = c; }
            else if(a > a3){ a3 = a; }
            int d = dd[c];
            if(d > d1){ d2 = d1; d1 = d; j1 = c; } else if(d > d2) d2 = d; }
        for(int e = head_[p]; e != -1; e = nxt_[e]){ int c = to_[e]; if(c == par[p]) continue;
            int b1 = (i1 == c) ? a2 : a1;                  // ระยะลงที่ยาวสุด ไม่นับกิ่งของ c
            int b2 = (i1 == c) ? a3 : ((i2 == c) ? a3 : a2);
            int bd = (j1 == c) ? d2 : d1;                  // เส้นผ่านศูนย์กลางของลูกตัวอื่น
            int s1 = uh[p], s2 = 0;                        // สองทางที่ยาวสุดจาก p รวมทางขึ้นข้างบน
            if(b1 > s1){ s2 = s1; s1 = b1; } else s2 = b1;
            if(b2 > s2) s2 = b2;
            ud[c] = max(max(ud[p], bd), s1 + s2);
            uh[c] = 1 + max(uh[p], b1); } }

    int best = INT_MAX, bv = -1;
    for(int v = 2; v <= N; v++){
        int d1 = dd[v], d2 = ud[v];
        int s = max(max(d1, d2), (d1 + 1) / 2 + (d2 + 1) / 2 + 1);
        if(s < best){ best = s; bv = v; } }

    // รู้แล้วว่าปิดเส้นไหน จึงค่อยเดินกว้างสองรอบต่อข้าง เพื่อหาจุดกึ่งกลางจริง ๆ
    int pu = par[bv];
    vector<int> d(N + 1, -1), pa(N + 1, 0), seen;
    auto centerOf = [&](int s) -> int {
        fill(d.begin(), d.end(), -1); bfs(s, pu, bv, d, pa, seen);
        int u = s; for(int x : seen) if(d[x] > d[u]) u = x;
        fill(d.begin(), d.end(), -1); bfs(u, pu, bv, d, pa, seen);
        int w = u; for(int x : seen) if(d[x] > d[w]) w = x;
        int steps = d[w] / 2, cur = w; while(steps--) cur = pa[cur];
        return cur; };
    printf("%d\n%d %d\n%d %d\n", best, pu, bv, centerOf(bv), centerOf(pu));
}

// ตัวตรวจ ปิดทุกเส้น ต่อทุกคู่ห้อง แล้ววัดระยะไกลสุดจริงทุกครั้ง
// ไม่มีคำว่ารัศมีหรือจุดกึ่งกลางอยู่ในนี้เลย
#include <bits/stdc++.h>
using namespace std;
int N; vector<pair<int,int>> E;
int diamOf(vector<vector<int>>&g, vector<int>&comp){
    int best = 0;
    for(int s : comp){ vector<int> d(N + 1, -1); queue<int> q; q.push(s); d[s] = 0;
        while(!q.empty()){ int u = q.front(); q.pop();
            for(int v : g[u]) if(d[v] < 0){ d[v] = d[u] + 1; q.push(v); } }
        for(int v : comp) best = max(best, d[v]); }
    return best; }
int main(){
    scanf("%d", &N); E.resize(N - 1);
    for(auto &e : E) scanf("%d %d", &e.first, &e.second);
    int ans = INT_MAX;
    for(int rm = 0; rm < N - 1; rm++){
        vector<vector<int>> g(N + 1);
        for(int i = 0; i < N - 1; i++) if(i != rm){
            g[E[i].first].push_back(E[i].second); g[E[i].second].push_back(E[i].first); }
        vector<int> col(N + 1, 0), A, B;
        { queue<int> q; q.push(E[rm].first); col[E[rm].first] = 1;
          while(!q.empty()){ int u = q.front(); q.pop(); A.push_back(u);
            for(int v : g[u]) if(!col[v]){ col[v] = 1; q.push(v); } } }
        for(int v = 1; v <= N; v++) if(!col[v]) B.push_back(v);
        for(int x : A) for(int y : B){
            g[x].push_back(y); g[y].push_back(x);
            vector<int> all; for(int v = 1; v <= N; v++) all.push_back(v);
            ans = min(ans, diamOf(g, all));
            g[x].pop_back(); g[y].pop_back(); } }
    printf("%d\n", ans);
}