Firstly, let's find some diameter of the tree. Let a and b be the endpoints of this diameter (and first two vertices of the answer). You can prove yourself why it is always good to take the diameter and why any diameter can be taken in the answer. Then there are two cases: the length of the diameter is n−1 or the length of the diameter is less than n−1. In the first case, you can take any other vertex as the third vertex of the answer c, it will not affect the answer anyway. Otherwise, we can run multi-source bfs from all vertices of the diameter and take the farthest vertex as the third vertex of the answer. It is always true because we can take any diameter and the farthest vertex will increase the answer as much as possible.

pragma GCC optimize("Ofast")

pragma GCC target("avx,avx2,fma")

include <bits/stdc++.h>

include<ext/pb_ds/assoc_container.hpp>

include<ext/pb_ds/tree_policy.hpp>

using namespace std; using namespace chrono; using namespace __gnu_pbds;

define int long long

define all(a) a.begin(),a.end()

define endl "\n"

define pb push_back

define pii pair<int , int>

define ff first

define ss second

define input(a) for(auto &it : a)cin >> it;

define output(a) for(auto it : a)cout << it << " ";

define FOR_IN(a, b , v) for(int i = a ; i < b ; i++) cin >> v[i];

define FOR_OUT(a, b , v) for(int i = a ; i < b ; i++) cout << v[i] << " ";

define fill(a,b) memset(a, b, sizeof(a))

int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;} int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;} int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a — b) % m) + m) % m;} int ceil(int n , int k) {return ((n + k — 1) / k);}

const int maxN = 1e5 + 10; const int maxN2 = 2 * 1e5 + 10; const int maxN3 = 1e6 + 10; const int INF = 1e18; int mod = 1e9 + 7;

ifndef ONLINE_JUDGE

define debug(x) \

cerr << (#x) << " is ";\ _print(x)

define dbg(x) \

cerr << (#x) << " is " << x << endl;

else

define debug(x)

define dbg(x)

endif

using ull = unsigned long long; using lld = long double; typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

void _print(int t) {cerr << t;} void _print(string t) {cerr << t;} void _print(char t) {cerr << t;} void _print(lld t) {cerr << t;} void _print(double t) {cerr << t;} void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p); template void _print(vector v); template void _print(set v); template <class T, class V> void _print(map <T, V> v); template void _print(multiset v); template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; cerr << endl;} template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;} template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;} template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;} template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;} void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}

// Memory Exceed || Time Exceed --> Reason Canbe long long vectoradj[maxN2]; vectordepth , dist; vectorpath , level; vectornew_depth; void dfs1(int u , int p) { for (auto v : adj[u]) { if (v == p)continue; dist[v] = min(dist[v] , dist[u] + 1); dfs1(v , u); } } void dfs2(int u , int p , int target , vector ans) { ans.push_back(u); for (auto v : adj[u]) { if (v == p)continue; dfs2(v, u, target , ans); } if (u == target) { path = ans; } ans.pop_back(); } void dfs3(int u , int p) { for (auto v : adj[u]) { if (v == p) continue; dfs3(v , u); depth[u] = max(depth[u] , 1 + depth[v]); } } void dfs4(int u , int p , int lvl , int & w) { if (lvl == 0) { w = u; return; } for (auto v : adj[u]) { if (v == p)continue; dfs4(v , u , lvl — 1 , w); } }

void new_dfs(int u , int p) { for (auto v : adj[u]) { if (v == p)continue; new_depth[v] = new_depth[u] + 1; new_dfs(v , u); } } void solve() { int n ; cin >> n; for (int i = 0 ; i < n — 1 ; i++) { int u , v ; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } depth.assign(n, 0); dist.assign(n, INF); dist[0] = 0; dfs1(0 , -1); int u = max_element(all(dist)) — dist.begin(); dist.assign(n, INF); dist[u] = 0; dfs1(u , -1); int v = max_element(all(dist)) — dist.begin(); dfs2(v , -1 , u , {}); int ans = path.size() — 1; int w = -1; depth.assign(n , 0); dfs3(v , 0); setst(all(path)); new_depth.assign(n , 0); for (int i = 1 ; i < path.size() — 1 ; i++) { int node = path[i]; for (auto v : adj[node]) { if (st.find(v) != st.end())continue; new_depth[v] = 1; new_dfs(v , node); } } if (path.size() == n) { for (auto p : path) { if (p == u || p == v)continue; w = p; break; } cout << ans << endl; cout << u + 1 << " " << v + 1 << " " << w + 1 << endl; return; } // debug(new_depth); cout << ans + *max_element(all(new_depth)) << endl; cout << u + 1 << " " << v + 1 << " " << (max_element(all(new_depth)) — new_depth.begin()) + 1 << endl; }

signed main () {

ifndef ONLINE_JUDGE

freopen("input.txt"  , "r", stdin);
freopen("output.txt" , "w", stdout);
freopen("error.txt" , "w" , stderr);

endif

ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int t = 1;
// cin >> t;
while (t--)solve();

}