Problem: 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 ≤ n ≤ 2 ⋅ 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 ≤ u_i, v_i ≤ n, u_i ≠ 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: <image>

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: <image>

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
const int maxn = 2e5 + 5;
const int logn = 20;
int n;
vector<int> adj[maxn];
int lev[maxn];
int par[logn][maxn];
int used[maxn];
void dfs(int u, int p) {
  for (int i = (1); i < (logn); ++i) par[i][u] = par[i - 1][par[i - 1][u]];
  for (int v : adj[u]) {
    if (v != p) {
      lev[v] = lev[u] + 1;
      par[0][v] = u;
      dfs(v, u);
    }
  }
}
int lca(int u, int v) {
  if (lev[u] < lev[v]) swap(u, v);
  for (int i = (logn)-1; i >= (0); --i) {
    if (lev[par[i][u]] >= lev[v]) {
      u = par[i][u];
    }
  }
  if (u == v) return u;
  for (int i = (logn)-1; i >= (0); --i) {
    if (par[i][u] != par[i][v]) {
      u = par[i][u];
      v = par[i][v];
    }
  }
  return par[0][u];
}
pair<int, int> best;
int from[maxn];
void dfs(int u, int p, int lev) {
  chkmax(best, make_pair(lev, u));
  for (int v : adj[u]) {
    if (v != p && used[v]) {
      from[v] = u;
      dfs(v, u, lev + 1);
    }
  }
}
int center(int rt) {
  best = make_pair(0, 0);
  dfs(rt, -1, 0);
  int st = best.second;
  best = make_pair(0, 0);
  dfs(st, -1, 0);
  int ed = best.second;
  int len = best.first;
  for (int i = (0); i < (len >> 1); ++i) ed = from[ed];
  return ed;
}
int isleaf[maxn];
int ff[maxn];
void dfs2(int u, int p, int seanc = -1) {
  ff[u] = seanc;
  int num = 0;
  for (int v : adj[u]) {
    if (used[v]) {
      num++;
    }
    if (v != p && used[v]) {
      lev[v] = lev[u] + 1;
      int nseanc = seanc;
      if (nseanc == -1) nseanc = v;
      dfs2(v, u, nseanc);
    }
  }
  if (num == 1) {
    isleaf[u] = 1;
  }
}
pair<int, int> f[maxn];
pair<int, int> g[maxn];
void dfs3(int u, int p) {
  vector<pair<int, int> > vals;
  vals.push_back(make_pair(0, u));
  for (int v : adj[u]) {
    if (v != p && !used[v]) {
      dfs3(v, u);
      vals.push_back(make_pair(f[v].first + 1, f[v].second));
    }
  }
  sort((vals).begin(), (vals).end(), greater<pair<int, int> >());
  f[u] = vals[0];
  if (int((vals).size()) > 1) {
    g[u] = vals[1];
  } else {
    g[u] = make_pair(-INF, -INF);
  }
}
void chemthan() {
  cin >> n;
  for (int i = (0); i < (n - 1); ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v), adj[v].push_back(u);
  }
  dfs(0, -1);
  vector<int> ver;
  for (int u = (0); u < (n); ++u)
    if (int((adj[u]).size()) >= 3) ver.push_back(u);
  int rt = ver[0];
  for (int u : ver) rt = lca(rt, u);
  used[rt] = 1;
  for (int i = (0); i < (int((ver).size())); ++i) {
    int u = ver[i];
    while (u != rt && !used[u]) {
      used[u] = 1;
      u = par[0][u];
    }
  }
  rt = center(rt);
  dfs2(rt, -1);
  map<int, pair<pair<int, int>, pair<int, int> > > hs;
  vector<pair<pair<int, int>, pair<int, int> > > vals;
  for (int u = (0); u < (n); ++u)
    if (isleaf[u]) {
      dfs3(u, -1);
      chkmax(hs[ff[u]], make_pair(make_pair(lev[u], f[u].first + g[u].first),
                                  make_pair(f[u].second, g[u].second)));
    }
  for (auto it : hs) {
    vals.push_back(it.second);
  }
  sort((vals).begin(), (vals).end()), reverse((vals).begin(), (vals).end());
  cout << vals[0].second.first + 1 << " " << vals[1].second.first + 1 << "\n";
  cout << vals[0].second.second + 1 << " " << vals[1].second.second + 1 << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}