SMMR-143: Story of Pleng

/*
dp on graph
undirected graph
*/
#include <bits/stdc++.h>

using namespace std;
const int INF = 2e9;
const int N = 1e5;
vector <int> g[N+10];
int dp1[N+10], dp2[N+10];
bool visited[N+10], p[N+10];
int mx = 0, node;

int f(int u){
    if(visited[u]) return -INF;
    visited[u] = true;
    for(auto v: g[u]){
        if(visited[v]) continue;
        int dis = f(v) + 1;
        if(dis > dp1[u]){
            dp2[u] = dp1[u];
            dp1[u] = dis;
        }
        else dp2[u] = max(dp2[u], dis);
    }
    if(dp1[u] + dp2[u] - 1 > mx){
        mx = dp1[u] + dp2[u] - 1;
        node = u;
    }
    return dp1[u];
}

void prt2(int u, int d){
    if(d == 0) return;
    for(auto v: g[u]){
        if(v == u) continue;
        if(dp1[v] == d-1) {
            prt2(v, d-1);
            printf("%d ", u);
            p[u] = true;
            return;
        }
    }
    printf("%d ", u);
    p[u] = true;
}

void prt1(int u, int d){
    if(u != node) printf("%d ", u);
    for(auto v: g[u]){
        if(v == u) continue;
        if(dp1[v] == d-1 and !p[v]){
            prt1(v, d-1);
            return;
        }
    }
}

int main(){

    int n;
    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        dp1[i] = 1;
    }

    for(int i=1;i<n;i++){
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    f(1);

    printf("%d\n", mx);

    prt2(node, dp2[node]);
    prt1(node, dp1[node]);

    return 0;
}
/***
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2 9
9 10

5
1 2
2 3
2 4
2 5

4
1 2
2 3
3 4

21
1 2
2 3
2 6
3 4
3 5
6 7
6 8
8 9
8 14
9 10
9 11
11 12
11 13
14 15
14 19
15 16
15 17
15 18
19 20
20 21
***/