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

Your task is to choose three distinct vertices $a, b, c$ on this tree such that the number of edges which belong to at least one of the simple paths between $a$ and $b$, $b$ and $c$, or $a$ and $c$ 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 $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree. 

Next $n - 1$ lines describe the edges of the tree in form $a_i, b_i$ ($1 \le a_i$, $b_i \le n$, $a_i \ne b_i$). It is guaranteed that given graph is a tree.


-----Output-----

In the first line print one integer $res$ — the maximum number of edges which belong to at least one of the simple paths between $a$ and $b$, $b$ and $c$, or $a$ and $c$.

In the second line print three integers $a, b, c$ such that $1 \le a, b, c \le n$ and $a \ne, b \ne c, a \ne c$.

If there are several answers, you can print any.


-----Example-----
Input
8
1 2
2 3
3 4
4 5
4 6
3 7
3 8

Output
5
1 8 6



-----Note-----

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

[Image]

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

Difficulty: introductory

Starter code:

Solutions:
import sys
input = sys.stdin.readline

NEGINF = -1000000

n = int(input())
adj = [[] for i in range(n)]
parent = [-1] * n

visited = [False] * n
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

tup = tuple()
outs = [tup] * n
q = [(0, 0)]

while q:
    node, type = q.pop()
    if type == 0:
        visited[node] = True
        q.append((node, 1))
        for v in adj[node]:
            if not visited[v]:
                parent[v] = node
                q.append((v, 0))
    else:
        ones = [(0, node)]
        twos = []
        threes = []
        for v in adj[node]:
            if v != parent[node]:
                a, b, c = outs[v]
                ones.append((a[0] + 1, a[1], v))
                twos.append((b[0] + 1, b[1], v))
                threes.append(c)
        ones.sort(reverse = True)
        twos.sort(reverse = True)
        threes.sort(reverse = True)

        bestOne = (ones[0][0], ones[0][1])
        
        bestsTwo = [(NEGINF, (0, 0))]
        if len(twos) > 0:
            bestsTwo.append((twos[0][0], twos[0][1]))
        if len(ones) > 1:
            o1 = ones[0]
            o2 = ones[1]
            bestsTwo.append((o1[0] + o2[0], (o1[1], o2[1])))

        bestsThree = [(NEGINF, (0, 0, 0))]
        if len(threes) > 0:
            bestsThree.append(threes[0])
        if len(ones) > 2:
            o1 = ones[0]
            o2 = ones[1]
            o3 = ones[2]
            bestsThree.append((o1[0] + o2[0] + o3[0], (o1[1], o2[1], o3[1])))
        if len(twos) > 0:
            o1 = ones[0]
            t1 = twos[0]
            if o1[2] != t1[2]:
                bestsThree.append((o1[0] + t1[0], (o1[1], t1[1][0], t1[1][1])))
            else:
                if len(twos) > 1:
                    t2 = twos[1]
                    bestsThree.append((o1[0] + t2[0], (o1[1], t2[1][0], t2[1][1])))
                if len(ones) > 1:
                    o2 = ones[1]
                    bestsThree.append((o2[0] + t1[0], (o2[1], t1[1][0], t1[1][1])))
                    

        outs[node] = (bestOne, max(bestsTwo), max(bestsThree))

final = outs[0][2]
print(final[0])
print(' '.join([str(x + 1) for x in final[1]]))


import sys
from collections import deque

# inf = open('input.txt', 'r')
# reader = (line.rstrip() for line in inf)
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    v, to = list(map(int, input().split()))
    v -= 1
    to -= 1
    g[v].append(to)
    g[to].append(v)

# (vertex, distance)
queue = deque([(0, 0)])
visited = [False] * n
while queue:
    v, d = queue.popleft()
    visited[v] = True
    for to in g[v]:
        if not visited[to]:
            queue.append((to, d + 1))
a = v

# (vertex, distance)
queue = deque([(a, 0)])
prev = [-1] * n
for i in range(n):
    visited[i] = False
while queue:
    v, d = queue.popleft()
    visited[v] = True
    for to in g[v]:
        if not visited[to]:
            queue.append((to, d + 1))
            prev[to] = v
b, ctr = v, d

for i in range(n):
    visited[i] = False
curr = prev[b]
nxt = b
prv = prev[curr]
add = 0
if a != 0 and b != 0:
    c = 0
elif a != 1 and b != 1:
    c = 1
else:
    c = 2
while curr != a:
    visited[curr] = True
    for to in g[curr]:
        if to == nxt or to == prv:
            continue
        queue = deque([(to, 1)])
        while queue:
            v, d = queue.popleft()
            visited[v] = True
            for to in g[v]:
                if not visited[to]:
                    queue.append((to, d + 1))
        if add < d:
            c, add = v, d    
    nxt = curr
    curr = prev[curr]
    prv = prev[curr]
    
print(ctr + add)
print(a + 1, b + 1, c + 1)

# inf.close()


import sys
input = sys.stdin.readline

n=int(input())
E=[[] for i in range(n+1)]

for i in range(n-1):
    x,y=list(map(int,input().split()))
    E[x].append(y)
    E[y].append(x)

def dfs(t):
    L=[-1]*(n+1)
    L[t]=0

    Q=[t]

    while Q:
        x=Q.pop()
        for to in E[x]:
            if L[to]==-1:
                L[to]=L[x]+1
                Q.append(to)

    return L.index(max(L))

A=dfs(1)
B=dfs(A)

DEPTH=[-1]*(n+1)
DEPTH[1]=0

from collections import deque
QUE = deque([1])
QUE2 = deque()
EULER=[]

USED=[0]*(n+1)
while QUE:
    x=QUE.pop()
    EULER.append((DEPTH[x],x))
    if USED[x]==1:
        continue
    for to in E[x]:
        
        if USED[to]==0:
            DEPTH[to]=DEPTH[x]+1
            QUE2.append(to)
        else:
            QUE.append(to)
    QUE.extend(QUE2)
    QUE2=deque()
 
    USED[x]=1

MINP=[1<<30]*(n+1)
MAXP=[-1]*(n+1)

for ind,(depth,p) in enumerate(EULER):
    MINP[p]=min(MINP[p],ind)
    MAXP[p]=max(MAXP[p],ind)

LEN=len(EULER)

seg_el=1<<(LEN.bit_length())
SEG=[(1<<30,0)]*(2*seg_el)

for i in range(LEN):
    SEG[i+seg_el]=EULER[i]

for i in range(seg_el-1,0,-1):
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):
    i=n+seg_el
    SEG[i]=x
    i>>=1
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=(1<<30,0)

    while L<R:
        if L & 1:
            ANS=min(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=min(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

def LCA(l,r):
    return getvalues(min(MINP[l],MINP[r]),max(MAXP[l],MAXP[r])+1)

A2=DEPTH[A]*2+DEPTH[B]*2-LCA(A,B)[0]*2
ANS=0

for i in range(1,n+1):
    if i==A or i==B:
        continue

    if ANS<A2+DEPTH[i]*2-LCA(i,A)[0]*2-LCA(i,B)[0]*2:
        ANS=A2+DEPTH[i]*2-LCA(i,A)[0]*2-LCA(i,B)[0]*2
        Aind=i

print(ANS//2)
print(A,B,Aind)
    
    


import sys
from collections import deque
n = int(input())
adj = [[] for _ in range(n)]
for u, v in (list(map(int, l.split())) for l in sys.stdin):
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)

inf = 10**9


def rec(s):
    prev = [-1]*n
    prev[s] = inf
    dq = deque([s])
    last = s

    while dq:
        v = dq.popleft()
        last = v
        for dest in adj[v]:
            if prev[dest] > -1:
                continue
            prev[dest] = v
            dq.append(dest)

    return last, prev


v1, _ = rec(0)
v2, prev = rec(v1)
v = prev[v2]
visited = [0]*n
visited[v] = visited[v1] = visited[v2] = 1
dia = 0
max_e, max_e_i = 0, v

while v != inf:
    dia += 1
    if prev[v] != inf:
        visited[prev[v]] = 1

    stack = [(v, 0)]
    while stack:
        cv, e = stack.pop()
        if max_e < e:
            max_e, max_e_i = e, cv
        e += 1

        for dest in adj[cv]:
            if visited[dest]:
                continue
            visited[dest] = 1
            stack.append((dest, e))

    v = prev[v]

print(dia + max_e)
print(v1+1, v2+1, max_e_i+1)