เกาะกับสะพาน: เมื่อรูปของกราฟถูกล็อกไว้แล้ว เส้นทางยาวสุดเหลือแค่สองทรง

ก่อนจะเลือกวิธี ต้องรู้ก่อนว่าแผนที่หน้าตาเป็นยังไง ลองทำตามใบ้ คือวาดลูกศรจากแต่ละเกาะไปเกาะที่สะพานของมันชี้ถึง

ทุกเกาะมีลูกศรออกเส้นเดียว เดินตามลูกศรไปเรื่อย ๆ เกาะมีจำกัด สักวันต้องวนกลับมาเจอเกาะที่เคยผ่าน ทางที่วนนั้นคือวง (cycle อ่านว่า "ไซเคิล")

เกาะที่ไม่ได้อยู่บนวงก็เดินตามลูกศรไปจบที่วงเหมือนกัน มันจึงเป็นกิ่งที่ห้อยเข้าหาวง เรียกว่าต้นไม้ห้อย

กลุ่มที่มี k เกาะจะมีสะพาน k เส้นพอดี (สะพานของแต่ละเกาะอยู่ในกลุ่มของมันเอง) จึงมีวงได้แค่วงเดียว

จากรูป ทางที่ยาวที่สุดในกลุ่มหนึ่งมีได้แค่สองทรง

• ทรงจมในต้นไม้ อยู่ในต้นไม้ห้อยต้นเดียว ไม่ใช้สะพานบนวงเลยสักเส้น
• ทรงข้ามวง ลงต้นไม้ที่เกาะบนวงเกาะหนึ่ง ไต่วงไปทางเดียว แล้วลงต้นไม้ที่เกาะบนวงอีกเกาะ ไต่ได้ทางเดียวเพราะถ้าไต่ครบรอบก็ต้องเหยียบเกาะเดิมซ้ำ

ในตัวอย่าง ทั้งสองกลุ่มชนะด้วยทรงข้ามวง ส่วนชุดที่ 4 ของเกมคือแผนที่ที่ทรงจมในต้นไม้ชนะ ถ้าเล่นชุดนั้นจนได้คำตอบเต็มแล้ว จะเห็นว่าทางยาวสุดของมันไม่แตะวงเลย

รู้รูปแล้ว ไล่จากวิธีที่ตรงที่สุดก่อน โจทย์แบ่งคะแนนไว้สองชุด

วิธีที่ 2 ต้องใช้เรื่องเดียวจากรูปของแผนที่ คือทางที่ไม่ซ้ำเกาะไต่วงได้ทางเดียว มันจึงไม่ใช้สะพานบนวงอย่างน้อยหนึ่งเส้นเสมอ

งั้นลองตัดสะพานบนวงทิ้งทีละเส้น ตัดแล้วกลุ่มกลายเป็นต้นไม้ (tree) ทันที ทางที่ยาวที่สุดในต้นไม้มีชื่อว่าเส้นผ่านศูนย์กลาง (diameter อ่านว่า "ไดแอมิเทอร์")

เส้นผ่านศูนย์กลางของต้นไม้หาได้ด้วยการเดินทั่วต้นไม้สองรอบ วิธีและเหตุผลอยู่ในหัวข้อท้ายหน้า (อีกท่าของเส้นผ่านศูนย์กลาง) สำหรับตอนนี้รู้แค่ว่าแต่ละครั้งที่ตัด เราเดินทั่วกลุ่มสองรอบ

// เฉลยชุดทดสอบย่อย N ไม่เกิน 4,000 (40 คะแนน)
// ความคิดหลัก: ตัดเส้นบนวงออกทีละเส้น กลุ่มนั้นจะกลายเป็นต้นไม้ทันที
// แล้วเส้นทางยาวสุดในต้นไม้ก็คือเส้นผ่านศูนย์กลาง ซึ่งหาได้ด้วยการค้นสองรอบ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct E { int to, w, id; };
vector<vector<E>> g;                                // กราฟไม่มีทิศ สะพานสองเส้นระหว่างเกาะคู่เดียวกันเป็นคนละเส้น จึงต้องมีหมายเลขกำกับ

pair<int,ll> farthest(int s, const vector<char>& alive, int banId) {
    vector<ll> d(n + 1, -1);
    d[s] = 0;
    vector<int> st{s};
    int bi = s; ll bd = 0;
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        for (auto& e : g[u]) {
            int v = e.to;
            if (!alive[v] || d[v] >= 0 || e.id == banId) continue;   // ข้ามสะพานเส้นที่ตัดทิ้ง
            d[v] = d[u] + e.w;
            if (d[v] > bd) { bd = d[v]; bi = v; }
            st.push_back(v);
        }
    }
    return {bi, bd};
}

int main() {
    scanf("%d", &n);
    vector<int> f(n + 1), L(n + 1);
    g.assign(n + 1, {});
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &f[i], &L[i]);
        g[i].push_back({f[i], L[i], i});
        g[f[i]].push_back({i, L[i], i});
    }
    vector<char> seen(n + 1, 0);
    ll ans = 0;
    for (int s = 1; s <= n; s++) {
        if (seen[s]) continue;
        // เก็บสมาชิกของกลุ่มนี้
        vector<int> comp; vector<char> alive(n + 1, 0);
        vector<int> st{s}; seen[s] = 1;
        while (!st.empty()) {
            int u = st.back(); st.pop_back(); comp.push_back(u); alive[u] = 1;
            for (auto& e : g[u]) if (!seen[e.to]) { seen[e.to] = 1; st.push_back(e.to); }
        }
        // หาวงด้วยการเดินตามลูกศรจนวนกลับมาที่เดิม
        vector<int> mark(n + 1, 0);
        int u = s; while (!mark[u]) { mark[u] = 1; u = f[u]; }
        vector<int> cyc; int v = u;
        do { cyc.push_back(v); v = f[v]; } while (v != u);
        ll best = 0;
        for (size_t i = 0; i < cyc.size(); i++) {
            int a = cyc[i];                           // สะพานหมายเลข a คือเส้นที่ออกจากเกาะ a
            auto p1 = farthest(a, alive, a);          // ตัดสะพานนั้นแล้วหาเส้นผ่านศูนย์กลางของต้นไม้
            auto p2 = farthest(p1.first, alive, a);
            best = max(best, p2.second);
        }
        ans += best;
    }
    printf("%lld\n", ans);
}

ท่านี้ตัดวงละ c ครั้ง และทุกครั้งค้นทั้งกลุ่ม ต้นทุนจึงเป็น c คูณขนาดกลุ่ม แย่ที่สุดคือแผนที่ทั้งหมดเป็นวงเดียวยาว N ได้ N² ลองเทียบกับงบเวลาดู

เกินหลายพันเท่าแบบนี้ ปรับนิดหน่อยไม่พอแน่ เป้าคือต้องแตะแต่ละเกาะแค่ไม่กี่ครั้ง (เวลาเชิงเส้น) วิธีที่ 2 ช้าเพราะค้นทั้งกลุ่มใหม่ทุกครั้งที่ตัด วิธีเต็มจึงแยกคิดทีละทรงแทน ให้แต่ละทรงคิดรอบเดียวจบ

เริ่มจากทรงที่ง่ายกว่า ทางทรงจมในต้นไม้จะมีเกาะที่อยู่สูงสุด (ใกล้วงที่สุด) อยู่หนึ่งเกาะ จากเกาะนั้นทางแตกลงไปได้ไม่เกินสองกิ่ง ทางยาวสุดจึงคือการต่อสองกิ่งที่ลึกที่สุดเข้าด้วยกัน

ถ้าเกาะ u มีลูกศรชี้ไปเกาะ p เรียก p ว่าพ่อ และ u ว่าลูก (ลูกอยู่ไกลวงกว่า)

จะได้ t1 กับ t2 ของเกาะหนึ่ง ต้องรู้ค่าของลูกทุกตัวก่อน วิธีที่ทำได้ในรอบเดียวคือปอกใบ เหมือนปอกหัวหอมทีละชั้นจากนอกเข้าใน ใบ (leaf) ในที่นี้คือเกาะที่ไม่มีลูกศรชี้เข้าเลย

1. นับว่าแต่ละเกาะมีลูกศรชี้เข้ากี่เส้น ใส่เกาะที่นับได้ศูนย์ลงคิว
2. หยิบเกาะ u ออกจากคิว ส่งกิ่ง t1[u] + ความยาวสะพานของ u ขึ้นไปให้พ่อ (บวกสะพานเพราะกิ่งที่มองจากพ่อต้องเดินข้ามสะพานนั้นลงมาก่อน) ถ้ายาวกว่า t1 หรือ t2 ของพ่อก็แทนที่
3. ลดตัวนับของเกาะนั้นลงหนึ่ง ถ้าเหลือศูนย์ แปลว่าลูกครบทุกตัวแล้ว ใส่มันลงคิว

เกาะบนวงไม่เคยเข้าคิว เพราะมีเกาะบนวงอีกเกาะชี้เข้าเสมอ และเกาะนั้นไม่เคยถูกปอก ส่วนเกาะในต้นไม้ห้อยเข้าคิวครบทุกเกาะ ใบเข้าตั้งแต่แรก แล้วไล่ขึ้นมา พอลูกทุกตัวถูกปอก ตัวนับของพ่อก็ลดถึงศูนย์

เกาะที่เข้าคิวแล้ว ลูกของมันส่งค่ามาครบทุกตัว t1 กับ t2 จึงไม่เปลี่ยนอีก และ t2 มาจากลูกคนละตัวกับ t1 เองโดยอัตโนมัติ เพราะลูกแต่ละตัวส่งค่าขึ้นมาแค่ครั้งเดียว

สังเกตว่า t1 ของเกาะบนวงคือความลึกของต้นไม้ที่ห้อยจากเกาะนั้น ทรงข้ามวงต้องใช้ค่านี้ต่อ ท่านี้ใช้แค่คิวกับลูปธรรมดา ไม่มีการเรียกฟังก์ชันซ้อน ซึ่งสำคัญตอนต้นไม้ลึกเป็นล้านชั้น (ดูหัวข้อโค้ด)

ปอกเสร็จแล้ว เหลือแต่เกาะบนวง และแต่ละเกาะรู้แล้วว่าต้นไม้ที่ห้อยจากมันลึกเท่าไร ทีนี้ทรงข้ามวงเหลือแค่เลือกเกาะบนวงสองเกาะกับทิศที่จะไต่

ทางที่ลงต้นไม้ที่ตำแหน่ง i แล้วไต่ตามลูกศรไปถึงตำแหน่ง j ยาวเท่ากับ

ปัญหาแรกคือทางที่ไต่ข้ามจุดเริ่ม เช่นไต่จากตำแหน่ง 2 วนกลับไปตำแหน่ง 0 ค่า P[j] − P[i] จะติดลบ ทั้งที่ระยะจริงเป็นบวก

เราทำแบบเดียวกัน คือคลี่วงเป็นสองรอบ ได้แถวยาว 2c ตำแหน่ง k คือเกาะเดียวกับตำแหน่ง k mod c (เศษของ k หารด้วย c) และ P สะสมต่อไปเรื่อย ๆ ไม่วนกลับเป็นศูนย์

ทุกทางทรงข้ามวงตอนนี้คือคู่ตำแหน่ง i < j บนแถวนี้ ที่ห่างกันไม่เกิน c − 1 เช่นไต่จากเกาะ 4 (ตำแหน่ง 2) ข้ามจุดเริ่มไปเกาะ 1 ก็คือคู่ตำแหน่ง 2 กับ 3 ได้ P[3] − P[2] = 4 เป็นบวกแล้ว

ไล่ทุกคู่ตรง ๆ ยังเป็น c² อยู่ดี และวงยาวได้ถึงล้าน ต้องตัดอีกชั้น โดยจับสูตรกลุ่มใหม่ แยกส่วนที่เป็นของ j ออกจากส่วนที่เป็นของ i

ช่วงนี้ขยับไปทางขวาทีละช่องตาม j เรียกว่าหน้าต่างเลื่อน (sliding window อ่านว่า "สไลดิง วินโดว์")

ค่ามากสุดในหน้าต่างเลื่อนหาได้ด้วยคิวที่เข้าออกได้สองหัว เรียกว่า deque (อ่านว่า "เด็ค" ย่อจาก double-ended queue) อ่านเรื่องนี้แบบละเอียดได้ที่บทหน้าต่างเลื่อน

คิวเก็บตำแหน่งเรียงจากเก่าไปใหม่ และเพราะทุกครั้งที่ใส่ตัวใหม่เราไล่ตัวที่ไม่มากกว่าออกจากท้ายก่อน ค่า d − P ในคิวจึงลดลงจากหัวไปท้ายเสมอ หัวคิวจึงเป็นค่ามากสุดของหน้าต่าง ทุกตำแหน่ง j ทำตามนี้

1. ทิ้งหัวคิวที่หลุดหน้าต่างแล้ว (ห่างจาก j เกิน c − 1)
2. หัวคิวคือ i ที่มี d − P มากที่สุด ใช้มันคิดค่าของคู่ที่จบที่ j
3. ใส่ j ลงท้ายคิว แต่ก่อนใส่ ไล่ตัวท้ายที่ d − P ไม่มากกว่าของ j ออกให้หมด

แต่ละตำแหน่งเข้าคิวครั้งเดียวและออกได้ครั้งเดียว ทั้งแถวยาว 2c จึงใช้เวลาเชิงเส้น ลองเดินดูกับกลุ่มที่ 1

กลุ่มที่ 2 มีวงสองเกาะ (2 กับ 7) ไม่มีต้นไม้ห้อย หน้าต่างยาวแค่ 1 คู่ที่ดีที่สุดคือไต่สะพานยาว 3 ได้ 3

// ค่าของเส้นทางที่ลงต้นไม้ที่ i ไต่วงไปทางเดียวจนถึง j แล้วลงต้นไม้ที่ j คือ
//     d[i] + d[j] + (P[j] - P[i])   =   (d[j] + P[j]) + (d[i] - P[i])
// ก้อนหลังไม่ขึ้นกับ j เลย จึงใช้หน้าต่างเลื่อนเก็บค่ามากสุดของมันได้
deque<int> dq;
for (int j = 0; j < 2 * c; j++) {
    while (!dq.empty() && dq.front() < j - (c - 1)) dq.pop_front();   // ไต่วงเกินรอบไม่ได้
    if (!dq.empty())
        local = max(local, d[j % c] + P[j] + d[dq.front() % c] - P[dq.front()]);
    ll cur = d[j % c] - P[j];
    while (!dq.empty() && d[dq.back() % c] - P[dq.back()] <= cur) dq.pop_back();
    dq.push_back(j);
}

คำตอบของแต่ละกลุ่มคือค่าที่มากกว่าระหว่างสองทรง ทรงข้ามวงคิดทีละวงอยู่แล้ว แต่ t1 + t2 คิดไว้ที่ทุกเกาะ รวมเกาะในต้นไม้ห้อย จึงต้องรู้ก่อนว่าเกาะแต่ละเกาะอยู่กลุ่มไหน

คิวของการปอกใบช่วยตรงนี้ ในคิว ลูกมาก่อนพ่อเสมอ ไล่คิวย้อนกลับจึงได้พ่อก่อนลูก แต่ละเกาะก็แค่ลอกหมายเลขกลุ่มของเกาะที่มันชี้ถึง

    // ... ปอกใบ เก็บ t1/t2 และหาคำตอบฝั่งที่ข้ามวงมาเรียบร้อยแล้ว ...

    for(int h=(int)q.size()-1;h>=0;h--) comp[q[h]]=comp[f[q[h]]];   // แจกหมายเลขกลุ่มลงต้นไม้ที่ห้อยอยู่

    ll best=0;
    for(int u=1;u<=n;u++) best=max(best,t1[u]+t2[u]);   // เส้นทางที่จมอยู่ในต้นไม้ห้อย คิดถูกแล้ว
    (void)best;                                        // <-- บรรทัดที่ผิด: คิดเสร็จแล้วทิ้ง ไม่ได้เอาไปสู้กับ res เลย

    ll ans=0; for(ll v:res) ans+=v;                    // res มีแต่คำตอบฝั่งที่ข้ามวง
    printf("%lld\n",ans);
}

6
3 3
6 3
6 3
6 10
4 5
2 1

4
2 2
1 1
1 6
1 5

ที่ N เป็นล้าน ทุกอย่างต้องเป็นอาเรย์แบน ๆ และห้ามเรียกฟังก์ชันตัวเองซ้อนกัน (recursion อ่านว่า "รีเคอร์ชัน") เพราะต้นไม้ที่ลึกล้านชั้นจะทำให้หน่วยความจำส่วนที่เก็บการเรียกซ้อน (stack) ล้น

คิวของการปอกใบเก็บเป็นเวกเตอร์เดียวโดยไม่ลบตัวที่หยิบไปแล้ว มันจึงใช้ได้สองต่อ ตอนเดินหน้ามันคือคิว และตอนไล่ย้อนกลับมันคือลำดับพ่อก่อนลูกที่ใช้แจกหมายเลขกลุ่ม

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<int> f(n+1),L(n+1),indeg(n+1,0);
    for(int i=1;i<=n;i++){ scanf("%d %d",&f[i],&L[i]); indeg[f[i]]++; }
    vector<ll> t1(n+1,0),t2(n+1,0);                  // สองกิ่งที่ลึกที่สุดของแต่ละปม
    vector<int> q; q.reserve(n);
    for(int i=1;i<=n;i++) if(!indeg[i]) q.push_back(i);
    for(size_t h=0;h<q.size();h++){                  // ปอกใบทิ้งทีละชั้น เหลือไว้แต่ปมบนวง
        int u=q[h],p=f[u]; ll v=t1[u]+L[u];
        if(v>t1[p]){ t2[p]=t1[p]; t1[p]=v; } else if(v>t2[p]) t2[p]=v;
        if(--indeg[p]==0) q.push_back(p);
    }
    vector<int> comp(n+1,-1); vector<ll> res;
    vector<char> done(n+1,0);
    vector<int> cyc; vector<ll> d,P; vector<int> W;
    for(int s=1;s<=n;s++){
        if(indeg[s]==0||done[s]) continue;
        int id=(int)res.size(); cyc.clear();
        for(int u=s; !done[u]; u=f[u]){ done[u]=1; cyc.push_back(u); comp[u]=id; }
        int c=(int)cyc.size();
        d.assign(c,0); W.assign(c,0);
        for(int i=0;i<c;i++){ d[i]=t1[cyc[i]]; W[i]=L[cyc[i]]; }
        P.assign(2*c,0);
        for(int i=1;i<2*c;i++) P[i]=P[i-1]+W[(i-1)%c];
        ll local=0; deque<int> dq;                   // หน้าต่างเลื่อน หาค่ามากสุดของ d[i]-P[i]
        for(int j=0;j<2*c;j++){
            while(!dq.empty() && dq.front()<j-(c-1)) dq.pop_front();
            if(!dq.empty()) local=max(local, d[j%c]+P[j] + d[dq.front()%c]-P[dq.front()]);
            ll cur=d[j%c]-P[j];
            while(!dq.empty() && d[dq.back()%c]-P[dq.back()]<=cur) dq.pop_back();
            dq.push_back(j);
        }
        res.push_back(local);
    }
    for(int h=(int)q.size()-1;h>=0;h--) comp[q[h]]=comp[f[q[h]]];   // แจกหมายเลขกลุ่มลงต้นไม้ที่ห้อยอยู่
    for(int u=1;u<=n;u++) res[comp[u]]=max(res[comp[u]],t1[u]+t2[u]);
    ll ans=0; for(ll v:res) ans+=v;
    printf("%lld\n",ans);
}

รวมทั้งหมดผมสุ่ม 1,500 ชุดเทียบเฉลยเต็มกับตัวไล่ทุกทาง และอีก 800 ชุดเทียบเฉลยเต็มกับเฉลยชุด 40 คะแนน ตรงกันทุกชุด

เวลาที่วัดได้บนเครื่องผม สวน 1,000,000 เกาะ แบบวงสั้นเยอะ ๆ ใช้ 235 มิลลิวินาที แบบวงเดียวยาวหนึ่งล้านใช้ 240 มิลลิวินาที จากลิมิต 2.2 วินาที

ทรงจมในต้นไม้หาเส้นผ่านศูนย์กลางด้วยการเก็บสองกิ่งที่ลึกที่สุด (DP บนต้นไม้) ซึ่งจำเป็นในข้อนี้ เพราะเราต้องใช้ความลึกรายเกาะไปคิดเรื่องวงต่อ

ถ้าโจทย์ถามแค่ตัวเลขเส้นผ่านศูนย์กลาง มีท่าที่เขียนสั้นกว่า และเป็นท่าที่โค้ดชุด 40 คะแนนใช้หลังตัดสะพานบนวง

1. เดินทั่วต้นไม้จากเกาะไหนก็ได้ สะสมระยะไปตามทาง แล้วหาเกาะที่ไกลที่สุด เรียกว่า a
2. เดินทั่วต้นไม้อีกรอบจาก a ระยะที่ไกลที่สุดคือเส้นผ่านศูนย์กลาง

บนต้นไม้ ระหว่างสองเกาะมีทางเดียว ลำดับที่เดินจึงไม่สำคัญ จะเดินลึกก่อนหรือกว้างก่อนก็ได้ระยะเท่ากัน

ถ้าสะพานไม่มีความยาว (นับเป็นจำนวนเส้น) ก็ใช้การค้นแบบกว้าง (BFS ย่อจาก breadth-first search อ่านว่า "เบรดท์เฟิสต์เสิร์ช" คือค้นทีละชั้นจากใกล้ไปไกล) แบบโค้ดข้างล่างได้

พอได้ปลายข้างหนึ่งแล้ว รอบที่สองก็แค่วัดจากปลายนั้นออกไปให้ไกลสุด บทพิสูจน์ต้องแยกกรณีว่าทางจากจุดเริ่มไป a ตัดกับเส้นผ่านศูนย์กลางหรือไม่ หน้านี้ขอข้ามไป และใช้ตัวตรวจข้างล่างยืนยันแทน

// เส้นผ่าศูนย์กลางของต้นไม้ ด้วย BFS สองรอบ
// รอบแรกจากปมใดก็ได้ หาปมที่ไกลสุด รอบสองเริ่มจากปมนั้น ระยะที่ไกลสุดคือคำตอบ
// อินพุต: n แล้ว n-1 บรรทัด u v   เอาต์พุต: ความยาวเส้นผ่าศูนย์กลาง (นับเป็นจำนวนเส้น)
#include <bits/stdc++.h>
using namespace std;

/** คืนคู่ (ปมที่ไกลสุด, ระยะถึงปมนั้น) เมื่อเริ่มจาก s */
pair<int, int> far(int s, const vector<vector<int>>& g) {
    int n = (int)g.size();
    vector<int> dist(n, -1);
    dist[s] = 0;
    vector<int> q{s};
    for (int h = 0; h < (int)q.size(); h++)
        for (int v : g[q[h]])
            if (dist[v] == -1) {
                dist[v] = dist[q[h]] + 1;
                q.push_back(v);
            }
    int best = s;
    for (int i = 0; i < n; i++) if (dist[i] > dist[best]) best = i;
    return {best, dist[best]};
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<vector<int>> g(n);
    for (int i = 0; i + 1 < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (n == 1) { printf("0\n"); return 0; }
    int a = far(0, g).first;      // ปมปลายทางหนึ่งของเส้นผ่าศูนย์กลาง
    printf("%d\n", far(a, g).second);
    return 0;
}

// ตัวตรวจอิสระของเส้นผ่าศูนย์กลาง: BFS จากทุกปม เอาระยะที่มากที่สุดของทั้งหมด
// ไม่ใช้ข้ออ้างว่า "ปมที่ไกลสุดจากปมใดก็ได้ เป็นปลายของเส้นผ่าศูนย์กลาง" เลย
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<vector<int>> g(n);
    for (int i = 0; i + 1 < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int best = 0;
    for (int s = 0; s < n; s++) {
        vector<int> dist(n, -1);
        dist[s] = 0;
        vector<int> q{s};
        for (int h = 0; h < (int)q.size(); h++)
            for (int v : g[q[h]])
                if (dist[v] == -1) {
                    dist[v] = dist[q[h]] + 1;
                    q.push_back(v);
                }
        for (int i = 0; i < n; i++) best = max(best, dist[i]);
    }
    printf("%d\n", best);
    return 0;
}