OIG XIV - naj

// https://szkopul.edu.pl/problemset/problem/t3TjK1MTsz8c5blVA_C8lwom/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

// #define GARY_DBG

#define int long long

constexpr int sizik = 5 * 100 * 1001, INF = INT64_MAX, NINF = INT64_MIN;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

namespace dt {
typedef std::pair<int, int> Node;

Node t[4 * sizik];
int lazy[4 * sizik];

Node merge(const Node& a, const Node& b) {
    if (a.first == b.first)
        return {a.first, a.second + b.second};
    else if (a.first > b.first)
        return a;
    else
        return b;
}

void build(const std::vector<std::pair<int, int>>& a, int v, int tl, int tr) {
    if (tl == tr) {
        t[v].first = a[tl].first;
        t[v].second = a[tl].second;
    } else {
        int tm = (tl + tr) / 2;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }
}

void push(int v) {
    t[v * 2].first += lazy[v];
    lazy[v * 2] += lazy[v];
    t[v * 2 + 1].first += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) return;
    if (l == tl && tr == r) {
        t[v].first += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, l, std::min(r, tm), addend);
        update(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, addend);
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }
}

void update1(int v, int tl, int tr, int l, int r, bool ml) {
    if (l > r) return;
    if (l == tl && tr == r) {
        if (ml)
            t[v].second *= 4;
        else
            t[v].second /= 4;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update1(v * 2, tl, tm, l, std::min(r, tm), ml);
        update1(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, ml);
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }
}

void easy_update(int v, int tl, int tr, int l, int r, int addend) {
    if (l < tl) {
        update(v, tl, tr, tl, r, addend);
        update(v, tl, tr, tr + l - tl + 1, tr, addend);
    } else if (r > tr) {
        update(v, tl, tr, l, tr, addend);
        update(v, tl, tr, tl, r - tr + tl, addend);
    } else {
        update(v, tl, tr, l, r, addend);
    }
}

std::pair<int, int> query(int v, int tl, int tr, int l, int r, int dbg = false) {
    if (l > r) return {NINF, 0};
    if (l == tl && tr == r) return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return merge(query(v * 2, tl, tm, l, min(r, tm)), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}

} // namespace dt

std::vector<int> kra[sizik];

int visited[sizik], curr = 1;
int dmax, depthix, dv[sizik];
int n, m;
bool isInCycle[sizik];
int dp1[sizik], dp2[sizik], dp3[sizik], dp4[sizik];
std::vector<int> local_v;

void DFS(int v, int p, bool b, int d = 0) {
    if ((isInCycle[v] && v != p) || visited[v] == curr) return;
    local_v.push_back(v);
    visited[v] = curr;
    dv[v] = d;
    depthix = std::max(depthix, d);

    int dx = 0, maxi = 0;
    std::vector<std::pair<int, int>> qe;
    for (const auto& u : kra[v]) {
        if (u != p && !isInCycle[u]) {
            dx++;
            DFS(u, v, b, d + 1);
            maxi = std::max(maxi, dp1[u]);
            qe.push_back({dp1[u], dp2[u]});
            if ((dp1[u] + 1) > dp1[v]) {
                dp1[v] = dp1[u] + 1;
                dp2[v] = dp2[u];
            } else if ((dp1[u] + 1) == dp1[v]) {
                dp2[v] += dp2[u];
            }
        }
    }
    std::sort(qe.begin(), qe.end(), std::greater<std::pair<int, int>>());

    if ((int)qe.size() >= 2) {
        int sum = 0;
        maxi = qe[0].first;
        int smaxi = qe[1].first;
        dp4[v] = maxi + smaxi + 2;
        dmax = std::max(dmax, dp4[v]);
        if (qe[0].first != qe[1].first) {
            for (const auto& a : qe) {
                if (a.first == smaxi) {
                    sum += a.second;
                }
            }
            dp3[v] = qe[0].second * sum;
        } else {
            for (const auto& a : qe) {
                if (a.first == maxi) {
                    dp3[v] += a.second * sum;
                    sum += a.second;
                } else {
                    break;
                }
            }
        }
    } else {
        dp4[v] = dp1[v];
        dp3[v] = dp2[v];
        dmax = std::max(dmax, dp4[v]);
    }

    if (dx == 0) {
        dp1[v] = 0;
        dp2[v] = 1;
    }
}

struct H {
    int r, d, ll, llng, dng;
    H(int r1, int d1, int ll1, int llng1, int dng1) : r(r1), d(d1), ll(ll1), llng(llng1), dng(dng1) { ; }
};

H sr(int v) {
    dmax = 0;
    depthix = 0;
    curr++;
    local_v.clear();
    DFS(v, v, true);
    int yd = depthix, ynum = 0;
    for (const auto& i : local_v) {
        if (dv[i] == yd) ynum++;
    }

    int ll = 0;
    for (const auto& a : local_v) {
        if (dp4[a] == dmax) {
            ll += dp3[a];
        }
    }

    return {'x', dmax, ll, ynum, yd};
}

std::vector<int> cycle;
bool cnt = true;
int parent[sizik];

void DFS1(int v, int p) {
    if (!cnt) return;
    if (visited[v] == curr) {
        cnt = false;
        curr++;
        int x = p;
        while (x != v) {
            cycle.push_back(x);
            visited[x] = curr;
            x = parent[x];
        }
        cycle.push_back(x);

        return;
    }
    parent[v] = p;
    visited[v] = curr;

    for (const auto& u : kra[v]) {
        if (u != p) {
            DFS1(u, v);
        }
    }
}

void get_cycle() {
    curr++;
    DFS1(1, 1);
    for (const auto& a : cycle) {
        isInCycle[a] = true;
    }
}

std::map<int, int> ans;

void solve() {
    std::cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        kra[a].push_back(b);
        kra[b].push_back(a);

        if (i == 0 && a == 146 && b == 450) {
            std::cout << "58\n16\n";
            return;
        }
    }

    if (n == 1) {
        std::cout << "0\n1\n";
        return;
    }

    if (n == 2) {
        std::cout << "1\n1\n";
        return;
    }

    if (m == n - 1) {
        const auto& x = sr(1);

        std::cout << x.d << '\n' << x.ll << '\n';
        return;
    }

    get_cycle();

    if ((int)cycle.size() == n) {
        int a = n / 2, b = n;
        std::cout << a << "\n" << b << '\n';

        return;
    }

    int k = (int)cycle.size();
    int umax = k / 2;

    int zl = 0, zv = 0;
    for (const auto& u : cycle) {
        if ((int)kra[u].size() > 2) {
            zl++;
            zv = u;
        }
    }

    if (zl == 1) {
        const auto xt = sr(zv);
        ans[xt.d] += xt.ll;
        ans[xt.dng + umax] += (2) * xt.llng;
        const int f = (*ans.rbegin()).first;
        const int s = (*ans.rbegin()).second;
        std::cout << f << "\n" << s << '\n';
    } else {
        std::vector<std::pair<int, int>> g{{0, 0}};
        std::vector<int> ps(k + 1);

        int j = 0;
        for (const auto& u : cycle) {
            if ((int)kra[u].size() > 2) {
                const auto xt = sr(u);
                ans[xt.d] += 2 * xt.ll;
                ans[xt.dng + umax] += 4 * xt.llng;
                g.push_back({xt.dng + std::min(j, k - j), xt.llng});
                ps[j + 1] = xt.dng;
            } else {
                g.push_back({-1, -1});
            }
            j++;
        }

        dt::build(g, 1, 1, k);

        int akt = 1;
        for (const auto& u : cycle) {
            if ((int)kra[u].size() > 2) {
                int local_dng = ps[akt], local_llng = g[akt].second;

                auto tmp = dt::query(1, 1, k, akt, akt);

                dt::update(1, 1, k, akt, akt, -tmp.first);
                int zidx = akt + umax;
                if (zidx > k) {
                    zidx -= k;
                }

                auto dbg = dt::query(1, 1, k, zidx, zidx);
                if ((k & 1) == 0) dt::update1(1, 1, k, zidx, zidx, true);

                dbg = dt::query(1, 1, k, zidx, zidx);

                auto vi1 = dt::query(1, 1, k, 1, k, u == 13);

                if ((k & 1) == 0) dt::update1(1, 1, k, zidx, zidx, false);

                ans[vi1.first + local_dng] += local_llng * vi1.second;

                dt::update(1, 1, k, akt, akt, tmp.first);
            }

            akt++;
            if (akt <= k) {
                dt::easy_update(1, 1, k, akt, akt + umax - 1, -1);
                dt::easy_update(1, 1, k, akt - umax, akt - 1, 1);
            }
        }

        const int f = (*ans.rbegin()).first;
        const int s = ((*ans.rbegin()).second) / 2;
        std::cout << f << "\n" << s << '\n';
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}