You are given an undirected unweighted tree consisting of $n$ vertices.

An undirected tree is a connected undirected graph with $n - 1$ edges.

Your task is to choose two pairs of vertices of this tree (all the chosen vertices should be distinct) $(x_1, y_1)$ and $(x_2, y_2)$ in such a way that neither $x_1$ nor $y_1$ belong to the simple path from $x_2$ to $y_2$ and vice versa (neither $x_2$ nor $y_2$ should not belong to the simple path from $x_1$ to $y_1$).

It is guaranteed that it is possible to choose such pairs for the given tree.

Among all possible ways to choose such pairs you have to choose one with the maximum number of common vertices between paths from $x_1$ to $y_1$ and from $x_2$ to $y_2$. And among all such pairs you have to choose one with the maximum total length of these two paths.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

The length of the path is the number of edges in it.

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


-----Input-----

The first line contains an integer $n$ — the number of vertices in the tree ($6 \le n \le 2 \cdot 10^5$).

Each of the next $n - 1$ lines describes the edges of the tree.

Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

It is guaranteed that the given edges form a tree.

It is guaranteed that the answer with at least two common vertices exists for the given tree.


-----Output-----

Print any two pairs of vertices satisfying the conditions described in the problem statement.

It is guaranteed that it is possible to choose such pairs for the given tree.


-----Examples-----
Input
7
1 4
1 5
1 6
2 3
2 4
4 7

Output
3 6
7 5

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

Output
2 9
6 8

Input
10
6 8
10 3
3 7
5 8
1 7
7 2
2 9
2 8
1 4

Output
10 6
4 5

Input
11
1 2
2 3
3 4
1 5
1 6
6 7
5 8
5 9
4 10
4 11

Output
9 11
8 10



-----Note-----

The picture corresponding to the first example: [Image]

The intersection of two paths is $2$ (vertices $1$ and $4$) and the total length is $4 + 3 = 7$.

The picture corresponding to the second example: [Image]

The intersection of two paths is $2$ (vertices $3$ and $4$) and the total length is $5 + 3 = 8$.

The picture corresponding to the third example: $88^{\circ}$

The intersection of two paths is $3$ (vertices $2$, $7$ and $8$) and the total length is $5 + 5 = 10$.

The picture corresponding to the fourth example: $\$ 8$

The intersection of two paths is $5$ (vertices $1$, $2$, $3$, $4$ and $5$) and the total length is $6 + 6 = 12$.

Difficulty: interview

Starter code:

Solutions:
import sys

n = int(sys.stdin.readline())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = tuple(int(k) for k in sys.stdin.readline().split())
    i -= 1
    j -= 1
    edges[i].append(j)
    edges[j].append(i)

# Prunes the graph starting from the vertices with
# only 1 edge until we reach a vertex with 3+ edges.
# Stores the distance from each non-pruned vertex
# to each of the leaves it reaches.
def prune():
    pruned = [False for _ in range(n)]
    leaves = [[] for _ in range(n)]
    todo = []
    for i in range(n):
        if len(edges[i]) == 1:
            todo.append((0, i, i))
    while len(todo) > 0:
        d, i, j = todo.pop()
        pruned[j] = True
        for k in edges[j]:
            if not pruned[k]:
                if len(edges[k]) < 3:
                    todo.append((d + 1, i, k))
                else:
                    leaves[k].append((d + 1, i))
    return pruned, leaves

pruned, leaves = prune()

# Returns the furthest non-pruned vertices
# from another non-pruned vertex.
def furthest(i):
    assert not pruned[i]
    visited = list(pruned)
    top_distance = 0
    top_vertices = [i]
    todo = [(0, i)]
    while len(todo) > 0:
        d, i = todo.pop()
        visited[i] = True
        if d > top_distance:
            top_distance = d
            top_vertices = []
        if d == top_distance:
            top_vertices.append(i)
        for j in edges[i]:
            if not visited[j]:
                todo.append((d + 1, j))
    return top_distance, top_vertices

# Single center topology.
# Only 1 vertex with 3+ edges.
def solve_single_center(i):
    l = list(reversed(sorted(leaves[i])))[:4]
    return list(l[j][1] for j in range(4))

# Scores non-pruned vertices according to the sum
# of the distances to their two furthest leaves.
def vertices_score(v):
    scores = []
    for i in v:
        assert not pruned[i]
        l = list(reversed(sorted(leaves[i])))[:2]
        score = (l[0][0] + l[1][0]), l[0][1], l[1][1]
        scores.append(score)
    return list(reversed(sorted(scores)))

# Single cluster topology.
# 1 cluster of vertices, all equally far away from each other.
def solve_single_cluster(v):
    scores = vertices_score(v)[:2]
    return scores[0][1], scores[1][1], scores[0][2], scores[1][2]

# Double cluster topology.
# 2 clusters of vertices, pairwise equally far away from each other.
def solve_double_cluster(v1, v2):
    scores1 = vertices_score(v1)[:1]
    scores2 = vertices_score(v2)[:1]
    return scores1[0][1], scores2[0][1], scores1[0][2], scores2[0][2]

def solve():
    def start_vertex():
        for i in range(n):
            if not pruned[i]:
                return i
    i = start_vertex()
    distance, v1 = furthest(i)
    if distance == 0:
        return solve_single_center(v1[0])
    else:
        distance, v1 = furthest(v1[0])
        distance, v2 = furthest(v1[0])
        v = list(set(v1) | set(v2))
        if len(v) < len(v1) + len(v2):
            return solve_single_cluster(v)
        else:
            return solve_double_cluster(v1, v2)

a, b, c, d = solve()
print(a + 1, b + 1)
print(c + 1, d + 1)


import sys

n = int(sys.stdin.readline())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = tuple(int(k) for k in sys.stdin.readline().split())
    i -= 1
    j -= 1
    edges[i].append(j)
    edges[j].append(i)

# Prunes the graph starting from the vertices with
# only 1 edge until we reach a vertex with 3+ edges.
# Stores the distance from each non-pruned vertex
# to each of the leaves it reaches.
def prune():
    pruned = [False for _ in range(n)]
    leaves = [[] for _ in range(n)]
    todo = []
    for i in range(n):
        if len(edges[i]) == 1:
            todo.append((0, i, i))
    while len(todo) > 0:
        d, i, j = todo.pop()
        pruned[j] = True
        for k in edges[j]:
            if not pruned[k]:
                if len(edges[k]) < 3:
                    todo.append((d + 1, i, k))
                else:
                    leaves[k].append((d + 1, i))
    return pruned, leaves

pruned, leaves = prune()

# Returns the furthest non-pruned vertices
# from another non-pruned vertex.
def furthest(i):
    assert not pruned[i]
    visited = list(pruned)
    top_distance = 0
    top_vertices = []
    todo = [(0, i)]
    while len(todo) > 0:
        d, i = todo.pop()
        visited[i] = True
        if d > top_distance:
            top_distance = d
            top_vertices = []
        if d == top_distance:
            top_vertices.append(i)
        for j in edges[i]:
            if not visited[j]:
                todo.append((d + 1, j))
    return top_vertices

# Single center topology.
# Only 1 vertex with 3+ edges.
def solve_single_center(i):
    l = list(reversed(sorted(leaves[i])))[:4]
    return list(l[j][1] for j in range(4))

# Scores non-pruned vertices according to the sum
# of the distances to their two furthest leaves.
def vertices_score(v):
    scores = []
    for i in v:
        assert not pruned[i]
        l = list(reversed(sorted(leaves[i])))[:2]
        score = (l[0][0] + l[1][0]), l[0][1], l[1][1]
        scores.append(score)
    return list(reversed(sorted(scores)))

# Single cluster topology.
# 1 cluster of vertices, all equally far away from each other.
def solve_single_cluster(v):
    s = vertices_score(v)[:2]
    return s[0][1], s[1][1], s[0][2], s[1][2]

# Double cluster topology.
# 2 clusters of vertices, pairwise equally far away from each other.
def solve_double_cluster(v1, v2):
    s1 = vertices_score(v1)[:1]
    s2 = vertices_score(v2)[:1]
    return s1[0][1], s2[0][1], s1[0][2], s2[0][2]

def solve():
    def start_vertex():
        for i in range(n):
            if not pruned[i]:
                return furthest(i)[0]
    i = start_vertex()
    v1 = furthest(i)
    if len(v1) == 1 and v1[0] == i:
        return solve_single_center(v1[0])
    else:
        v2 = furthest(v1[0])
        v = list(set(v1) | set(v2))
        if len(v) < len(v1) + len(v2):
            return solve_single_cluster(v)
        else:
            return solve_double_cluster(v1, v2)

a, b, c, d = solve()
print(a + 1, b + 1)
print(c + 1, d + 1)


n=int(input())
degs=[0]*n
neighbors=[0]*n
children=[0]*n
useless=[0]*n
for i in range(n):
    neighbors[i]=[]
    children[i]=[]
for i in range(n-1):
    a,b=map(int,input().split())
    degs[a-1]+=1
    degs[b-1]+=1
    neighbors[a-1].append(b-1)
    neighbors[b-1].append(a-1)
for guy in range(n):
    if degs[guy]==1:
        useless[guy]+=1
        newguy=neighbors[guy][0]
        oldguy=guy
        depth=0
        while degs[newguy]==2:
            depth+=1
            useless[newguy]+=1
            if neighbors[newguy][0]==oldguy:
                oldguy=newguy
                newguy=neighbors[newguy][1]
            else:
                oldguy=newguy
                newguy=neighbors[newguy][0]
        children[newguy].append((depth,guy))
for guy in range(n):
    children[guy].sort(reverse=True)
newgraph={}
for i in range(n):
    if useless[i]==0:
        newgraph[i]=[]
for guy in newgraph:
    for guy1 in neighbors[guy]:
        if guy1 in newgraph:
            newgraph[guy].append(guy1)
dfs1={}
currlayer=[(list(newgraph)[0],None)]
currlevel=0
while len(currlayer)>0:
    for guy in currlayer:
        dfs1[guy[0]]=currlevel
    newlayer=[]
    for guy in currlayer:
        for vert in newgraph[guy[0]]:
            if vert!=guy[1]:
                newlayer.append((vert,guy[0]))
    currlayer=newlayer
    currlevel+=1
maxi=0
for guy in dfs1:
    maxi=max(maxi,dfs1[guy])
bestdist=0
bestvert=None
for guy in dfs1:
    if dfs1[guy]==maxi:
        score=children[guy][0][0]+children[guy][1][0]
        if score>=bestdist:
            bestdist=score
            bestvert=guy
dfs2={}
currlayer=[(bestvert,None)]
currlevel=0
while len(currlayer)>0:
    for guy in currlayer:
        dfs2[guy[0]]=currlevel
    newlayer=[]
    for guy in currlayer:
        for vert in newgraph[guy[0]]:
            if vert!=guy[1]:
                newlayer.append((vert,guy[0]))
    currlayer=newlayer
    currlevel+=1
maxi=0
for guy in dfs2:
    maxi=max(maxi,dfs2[guy])
bestdist=0
bestvert1=None
for guy in dfs2:
    if dfs2[guy]==maxi:
        score=children[guy][0][0]+children[guy][1][0]
        if score>=bestdist:
            bestdist=score
            bestvert1=guy
print(children[bestvert][0][1]+1,children[bestvert1][0][1]+1)
print(children[bestvert][1][1]+1,children[bestvert1][1][1]+1)