2019 NHSPC north1 pF

#pragma GCC optimized("Ofast, unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define X first
#define Y second
#define Push push_back
#define ALL(x) x.begin(), x.end()

using lli = long long;
using pll = pair<lli, lli>;
using Double = long double;
template<typename T>
using Vector = vector<vector<T>>;
template<typename T>
using prior = priority_queue<T>;

set<pair<int,int>> beside;
vector<int> vs[16];
vector<bool> used(16, false);
vector<int> color(16, 0);
vector<lli> ans(16, 0);

int maxn;

void dfs(int now) {
    if (now > maxn) {
        ++ans[color[1]];
//      for (int i = 1; i <= maxn; ++i) cout << color[i] << " ";
//      cout << "\n";
        return;
    }

    for (int i = 1; i <= maxn; ++i) {
        if (!used[i]) {
            bool flag = true;
            for (auto x : vs[now]) {
                if (beside.count({color[x], i})) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                used[i] = true;
                color[now] = i;
                dfs(now + 1);
                used[i] = false;
            }
        }
    }
}

bool cmp(pair<int,int> a, pair<int,int> b) {
    if (a.X == b.X) return a.Y < b.Y;
    return a.X < b.X;
}

int main() {
    IOS;

    int n, m;
    cin >> n >> m;

    if (n == 1) {
        cout << "1\n1\n";
        return 0;
    }
    if (n == 2) {
        cout << "1\n2\n";
        return 0;
    }
    if (m == 0) {
        lli _ans = 1;
        for (int i = 2; i < n*(n+1)/2; ++i) _ans *= i;
        cout << 1 << "\n";
        cout << _ans << "\n";
        return 0;
    }

    if (n >= 3) {
        int tok = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (j != 1) vs[tok].Push((i - 2) * (i - 1) / 2 + j - 1);
                if (j != i) vs[tok].Push((i - 2) * (i - 1) / 2 + j);
                if (j != 1) vs[tok].Push(tok - 1);
                ++tok;
            }
        }

        maxn = n * (n + 1) / 2;

        int a, b;
        vector<pair<int,int>> Size(maxn + 1, {0, 0});
        for (int i = 1; i <= maxn; ++i) Size[i].Y = i;

        for (int i = 0; i < m; ++i) {
            cin >> a >> b;
            beside.insert({a, b});
            beside.insert({b, a});
            ++Size[a].X;
            ++Size[b].X;
        }

        sort(ALL(Size), cmp);

        if (n == 5) {
            vector<pair<int,int>> REAL;
            for (int i = 1; i <= 4; ++i) {
                int j = Size[i].Y;
                used[j] = true;
                color[1] = j;
                dfs(2);
                used[j] = false;
                if (ans[j]) {
                    REAL.Push({ans[j], j});
                }
            }

            sort(ALL(REAL));
            cout << REAL[0].Y << "\n";
            cout << REAL[0].X << "\n";
            return 0;
        }
        else {
            vector<pair<int,int>> REAL;
            for (int i = 1; i <= maxn; ++i) {
                int j = Size[i].Y;
                used[j] = true;
                color[1] = j;
                dfs(2);
                used[j] = false;
                if (ans[j]) {
                    REAL.Push({ans[j], j});
                }
            }

            sort(ALL(REAL));
            cout << REAL[0].Y << "\n";
            cout << REAL[0].X << "\n";
            return 0;
//          for (int i = 1; i <= maxn; ++i) {
//              used[i] = true;
//              color[1] = i;
//              dfs(2);
//              used[i] = false;
//          }
        }

        lli minAns = 1E18, minTok = -1;
        for (int i = 1; i <= maxn; ++i) {
//          cout << "Color " << i << ": " << ans[i] << "\n";
            if (ans[i] == 0) continue;
            else if (ans[i] < minAns) {
                minAns = ans[i];
                minTok = i;
            }
        }

        cout << minTok << "\n";
        cout << minAns << "\n";
    }

    return 0;
}