D. Ashraf's Town
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ashraf and his two teammates want to live in a weird town that has $$$n$$$ houses connected by undirected roads such that any house can go to any other house passing through roads and every two houses have a unique path between them.

Ashraf had an argument with his teammates, so he wants to live as far from them as possible, so he wants to know which house he can choose for himself and the two houses he can choose for his two teammates, such that the sum of the number of roads from them to his house is maximum and the three houses are $$$distinct$$$.

Example of the first test case
Input

The first line of input consists of one integer $$$n$$$ $$$(3\leq{n}\leq{2\cdot10^5})$$$ , the number of houses in the town.

Then $$$n-1$$$ lines follow, the $$$i$$$-th line containing two integers $$$a_i$$$ , $$$b_i$$$ $$$(1\leq{a_i,b_i}\leq{n}$$$, $$$a_i\neq{b_i})$$$ — the two houses that the $$$i$$$-th road connect.

Output

In the first line print one integer, the number of the house that Ashraf will choose.

In the second line print two integers, the houses of the two teammates.

If there are multiple solutions, print any.

Examples
Input
3
1 2
1 3
Output
3
2 1
Input
4
1 2
1 3
1 4
Output
3
2 4
Note

In the first example, Ashraf will reside in house number $$$3$$$ and his two teammates will reside in house $$$1$$$ and $$$2$$$.

So Ashraf's distance to $$$house$$$ $$$1$$$ is equal to $$$1$$$

and Ashraf's distance to $$$house$$$ $$$2$$$ is equal to $$$2$$$

so the sum of distances $$$1+2= 3$$$ which is the maximum they can achieve.

There are multiple answers like Ashraf can reside in house 2 and the two teammates in houses 1 and 3 you can print any which maximizes the sum of the two distances