# 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.

```#include<bits/stdc++.h>
#define ll long long
#define rg register ll
using namespace std;
ll n;
struct node
{
ll to,next,val;
}edge;
inline void add(ll u,ll v,ll val)
{
edge[cnt].to=v;
edge[cnt].val=val;
}
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();
{
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()
{
cin>>n;
for(rg i=1;i<n;i++)
{
ll a,b;
cin>>a>>b;
}
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;
}```

0 条评论

• ### Educational Codeforces Round 81 (Rated for Div. 2) A. Display The Number

You have a large electronic screen which can display up to 998244353998244353 de...

• ### Codeforces Beta Round #14 (Div. 2)A. Letter

A boy Bob likes to draw. Not long ago he bought a rectangular graph (checked) sh...

• ### 2018-2019 ICPC, NEERC, Southern Subregional Contest D. Garbage Disposal

Enough is enough. Too many times it happened that Vasya forgot to dispose of gar...

• ### 移动购物应用的兴起

在大流行中，移动购物应用程序已成为在线零售业务的中心，显然，它们将继续存在。实际上，到2021年，移动电子商务或移动商务的销售额预计将占所有零售电子商务销售额的...

• ### Know Kubernetes — Pictorially

Recently, I started my Kubernetes journey and wanted to understand its internals...

• ### Qualcomm - SnapDragon Tech Summit - Key Note - About 5G

Qualcomm SnapDragon Tech Summit首日Keynote。 Qualcomm对5G现状和未来的理解，及其技术框架。非常重要。

• ### 开源工作报告显示更多的空缺，更少的人（IT）

Linux基金会和学习平台edX周一发布了最新的开源就业报告，自两年前的上一份报告以来，该报告更新了技术招聘情况。研究表明，尽管发生了大流行，但对开源技术技能的...

• ### Mutex VS. Semaphore

The key point is that mutexes should be used to protect shared resources, while ...

什么是SmartStack? SmartStack is an automated service discovery and registration fr...

### 活动推荐 