Codeforces Round #615 (Div. 3) F. Three Paths on a Tree

F. Three Paths on a Tree

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an unweighted tree with nn vertices. Recall that a tree is a connected undirected graph without cycles.

Your task is to choose three distinct vertices a,b,ca,b,c on this tree such that the number of edges which belong to at least one of the simple paths between aa and bb, bb and cc, or aa and cc is the maximum possible. See the notes section for a better understanding.

The simple path is the path that visits each vertex at most once.

Input

The first line contains one integer number nn (3≤n≤2⋅1053≤n≤2⋅105) — the number of vertices in the tree.

Next n−1n−1 lines describe the edges of the tree in form ai,biai,bi (1≤ai1≤ai, bi≤nbi≤n, ai≠biai≠bi). It is guaranteed that given graph is a tree.

Output

In the first line print one integer resres — the maximum number of edges which belong to at least one of the simple paths between aa and bb, bb and cc, or aa and cc.

In the second line print three integers a,b,ca,b,c such that 1≤a,b,c≤n1≤a,b,c≤n and a≠,b≠c,a≠ca≠,b≠c,a≠c.

If there are several answers, you can print any.

Example

input

Copy

8
1 2
2 3
3 4
4 5
4 6
3 7
3 8

output

Copy

5
1 8 6

Note

The picture corresponding to the first example (and another one correct answer):

If you choose vertices 1,5,61,5,6 then the path between 11 and 55 consists of edges (1,2),(2,3),(3,4),(4,5)(1,2),(2,3),(3,4),(4,5), the path between 11 and 66 consists of edges (1,2),(2,3),(3,4),(4,6)(1,2),(2,3),(3,4),(4,6) and the path between 55 and 66 consists of edges (4,5),(4,6)(4,5),(4,6). The union of these paths is (1,2),(2,3),(3,4),(4,5),(4,6)(1,2),(2,3),(3,4),(4,5),(4,6) so the answer is 55. It can be shown that there is no better answer.

题意：找出树上三个点，满足这三个点相互形成的简单路径的边并集最大

直觉告诉我们：有两个点一定是直径的两个端点，嗯，你没错，这两个点怎么求？随便找一个点bfs出来一个端点，然后再以这个端点bfs一次出来另一个端点，ok

剩下一个点如何确定？到两个点距离和最大即可，在两次bfs过程中保留两个端点到任意点的距离然后找这个最大值就好

#include<bits/stdc++.h>
#define ll long long
#define rg register ll
using namespace std;
ll n;
ll head[200005],cnt,dis[200005],vis[200005],maxdis,dis1[200005],dis2[200005];
struct node
{
    ll to,next,val;
}edge[400005];
inline void add(ll u,ll v,ll val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
inline ll bfs(ll x)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    queue<ll>q;
    q.push(x);
    vis[x]=1;
    ll now;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(rg i=head[now];~i;i=edge[i].next)
        {
            ll to=edge[i].to;
            if(!vis[to])
            {
                q.push(to);
                vis[to]=1;
                dis[to]=dis[now]+edge[i].val;
                maxdis=max(maxdis,dis[to]);
            }
        }
    }
    return now;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n;
    for(rg i=1;i<n;i++)
    {
        ll a,b;
        cin>>a>>b;
        add(a,b,1),add(b,a,1);
    }
    ll ans1=bfs(1);
    ll ans2=bfs(ans1);
    for(rg i=1;i<=n;i++)dis1[i]=dis[i];
    bfs(ans2);
    for(rg i=1;i<=n;i++)dis2[i]=dis[i];
    ll ans3=0,ans=0;
    for(rg i=1;i<=n;i++)
    {
        if((dis1[i]+dis2[i]+maxdis)/2>ans&&i!=ans1&&i!=ans2)ans=(dis1[i]+dis2[i]+maxdis)/2,ans3=i;
    }
    cout<<ans<<endl<<ans1<<" "<<ans2<<" "<<ans3<<endl;
    while(1)getchar();
    return 0;
}