Fedor runs for president of Byteland! In the debates, he will be asked how to solve Byteland's transport problem. It's a really hard problem because of Byteland's transport system is now a tree (connected graph without cycles). Fedor's team has found out in the ministry of transport of Byteland that there is money in the budget only for one additional road. In the debates, he is going to say that he will build this road as a way to maximize the number of distinct simple paths in the country. A simple path is a path which goes through every vertex no more than once. Two simple paths are named distinct if sets of their edges are distinct. 

But Byteland's science is deteriorated, so Fedor's team hasn't succeeded to find any scientists to answer how many distinct simple paths they can achieve after adding exactly one edge on the transport system?

Help Fedor to solve it.

An edge can be added between vertices that are already connected, but it can't be a loop.

In this problem, we consider only simple paths of length at least two.

Input

The first line contains one integer n (2 ≤ n ≤ 500\ 000) — number of vertices in Byteland's transport system.

Each of the following n - 1 lines contains two integers v_i and u_i (1 ≤ v_i, u_i ≤ n). It's guaranteed that the graph is tree.

Output

Print exactly one integer — a maximal number of simple paths that can be achieved after adding one edge.

Examples

Input


2
1 2


Output


2


Input


4
1 2
1 3
1 4


Output


11


Input


6
1 2
1 3
3 4
3 5
4 6


Output


29
#include <bits/stdc++.h>
template <typename T>
void read(T &);
template <typename T>
void write(const T &);
const int iinf = 2147483647;
const long long llinf = 9223372036854775807ll;
const int N = 500005;
void dfs1(int u, int fa);
void dfs2(int u, int fa);
std::vector<int> G[N];
int siz[N];
long long ans[N];
int n;
int main() {
  read(n);
  for (int i = 1; i < n; ++i) {
    int u, v;
    read(u), read(v);
    G[u].push_back(v), G[v].push_back(u);
  }
  dfs1(1, 0);
  ans[1] = 1ll * n * (n - 1) / 2;
  dfs2(1, 0);
  int as = 1;
  for (int i = 2; i <= n; ++i) {
    if (ans[i] > ans[as]) as = i;
  }
  dfs1(as, 0);
  ans[as] = 1ll * n * (n - 1) / 2;
  dfs2(as, 0);
  as = 1;
  for (int i = 2; i <= n; ++i) {
    if (ans[i] > ans[as]) as = i;
  }
  write(ans[as]), putchar('\n');
  return 0;
}
void dfs1(int u, int fa) {
  siz[u] = 1;
  for (int v : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    siz[u] += siz[v];
  }
}
void dfs2(int u, int fa) {
  for (int v : G[u]) {
    if (v == fa) continue;
    ans[v] = ans[u] + 1ll * siz[v] * (siz[u] - siz[v]);
    dfs2(v, u);
  }
}
template <typename T>
void read(T &Re) {
  T k = 0;
  char ch = getchar();
  int flag = 1;
  while (!(ch >= '0' && ch <= '9')) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while ((ch >= '0' && ch <= '9')) k = k * 10 + ch - '0', ch = getchar();
  Re = flag * k;
}
template <typename T>
void write(const T &Wr) {
  if (Wr < 0) {
    putchar('-'), write(-Wr);
  } else if (Wr < 10) {
    putchar(Wr + '0');
  } else {
    write(Wr / 10), putchar((Wr % 10) + '0');
  }
}
