Imagine a city with n junctions and m streets. Junctions are numbered from 1 to n.

In order to increase the traffic flow, mayor of the city has decided to make each street one-way. This means in the street between junctions u and v, the traffic moves only from u to v or only from v to u. 

The problem is to direct the traffic flow of streets in a way that maximizes the number of pairs (u, v) where 1 ≤ u, v ≤ n and it is possible to reach junction v from u by passing the streets in their specified direction. Your task is to find out maximal possible number of such pairs.

Input

The first line of input contains integers n and m, (<image>), denoting the number of junctions and streets of the city.

Each of the following m lines contains two integers u and v, (u ≠ v), denoting endpoints of a street in the city.

Between every two junctions there will be at most one street. It is guaranteed that before mayor decision (when all streets were two-way) it was possible to reach each junction from any other junction.

Output

Print the maximal number of pairs (u, v) such that that it is possible to reach junction v from u after directing the streets.

Examples

Input

5 4
1 2
1 3
1 4
1 5


Output

13


Input

4 5
1 2
2 3
3 4
4 1
1 3


Output

16


Input

2 1
1 2


Output

3


Input

6 7
1 2
2 3
1 3
1 4
4 5
5 6
6 4


Output

27

Note

In the first sample, if the mayor makes first and second streets one-way towards the junction 1 and third and fourth streets in opposite direction, there would be 13 pairs of reachable junctions: {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x20202020;
const long long mod = 1000000007;
const double eps = 1e-9;
const double pi = 3.1415926535897932384626;
const int DX[] = {1, 0, -1, 0}, DY[] = {0, 1, 0, -1};
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long powmod(long long a, long long b, long long mod) {
  long long res = 1;
  a %= mod;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int N = 2010;
int dfn[N], low[N], vis[N], sta[N], bel[N], ps[N], sz[N];
int g[N][N], G[N][N];
vector<int> son[N];
int ans, n, m, tot, top, u, v, bs;
void dfss(int u, int f) {
  dfn[u] = low[u] = ++tot;
  vis[u] = 1;
  sta[top++] = u;
  for (int v = 1; v < n + 1; v++)
    if (g[u][v]) {
      if (v == f) continue;
      if (!vis[v]) dfss(v, u);
      low[u] = min(low[u], low[v]);
    }
  if (dfn[u] == low[u]) {
    ++m;
    while (1) {
      bel[sta[top - 1]] = m;
      ps[m]++;
      if (sta[--top] == u) break;
    }
  }
}
int ddfs(int u) {
  int ret = ps[u];
  vis[u] = 1;
  for (int v = 1; v < m + 1; v++)
    if (G[u][v] && !vis[v]) ret += ddfs(v);
  return ret;
}
inline int C(int n) { return n * (n - 1) / 2; }
void gao(vector<int> &c, int sm) {
  bitset<2010> dp;
  dp[0] = 1;
  for (int i = 0; i < ((int)(c).size()); i++)
    dp |= (dp << c[i]), ans += C(c[i]);
  int s = sm / 2;
  for (int i = s + 1 - 1; i >= 0; i--)
    if (dp[i]) {
      ans -= C(i) + C(sm - i);
      return;
    }
}
void dfs(int u, int f) {
  sz[u] = ps[u];
  bs += ps[u] * ps[u];
  for (int v = 1; v < m + 1; v++)
    if (G[u][v] && v != f) {
      dfs(v, u);
      sz[u] += sz[v];
      son[u].push_back(sz[v]);
    }
  son[u].push_back(n - sz[u]);
  gao(son[u], n - ps[u]);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    g[u][v] = g[v][u] = 1;
  }
  m = 0;
  for (int i = 1; i < n + 1; i++)
    if (!vis[i]) dfss(i, 0);
  for (int i = 1; i < n + 1; i++)
    for (int j = 1; j < n + 1; j++)
      if (bel[i] != bel[j] && g[i][j]) G[bel[i]][bel[j]] = 1;
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i < m + 1; i++)
    if (!vis[i]) {
      n = ddfs(i);
      bs += n * n;
      dfs(i, 0);
    }
  printf("%d\n", ans + bs / 2);
}
