#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/random>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using str = string;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
const ll INF = 1e18, MOD = 1e9 + 7;
#define int long long

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
        cout << "\n";
    }
}

vector<vector<int>> g;
vector<bool> us;

void dfs(int u) {
    us[u] = true;
    for (auto to: g[u]) {
        if (!us[to]) {
            dfs(to);
        }
    }
}

vector<int> get(int n, int m, vector<pair<int, int>> edge) {
    g.clear();
    g.resize(n);
    vector<vector<bool>> us1(n, vector<bool>(n));
    for (int i = 0; i < m; ++i) {
        g[edge[i].first].push_back(edge[i].second);
    }
    for (int i = 0; i < n; ++i) {
        us.clear();
        us.resize(n);
        dfs(i);
        for (int j = 0; j < n; ++j) {
            us1[i][j] = us[j];
        }
    }
    vector<int> col(n);
    for (int i = 0; i < n; ++i) {
        col[i] = i;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (us1[i][j] && us1[j][i]) {
                col[j] = col[i];
            }
        }
    }
    map<int, int> u;
    int o = 0;
    for (int i = 0; i < n; ++i) {
        if (u.find(col[i]) == u.end()) {
            u[col[i]] = o;
            o++;
        }
        col[i] = u[col[i]];
    }
    return col;
}

void solve() {
    int n, m, gg;
    cin >> n >> m >> gg;
    vector<pair<int, int>> edge(m);
    for (int i = 0; i < m; ++i) {
        cin >> edge[i].first >> edge[i].second;
        edge[i].first--;
        edge[i].second--;
    }
    vector<int> col = get(n, m, edge);
    vector<int> cnt1(m + 1);
    vector<vector<bool>> f((1 << (m / 2)), vector<bool>(1 << (m - (m / 2))));
    int mx = 0;
    for (int i = 0; i < (1 << m); ++i) {
        bool p = true;
        for (int j = 0; j < (1 << (m / 2)); ++j) {
            if ((i & j) == j) {
                if (f[j][i >> (m / 2)]) {
                    p = false;
                    break;
                }
            }
        }
        if (!p) {
            continue;
        }
        vector<int> pos;
        int i1 = i;
        for (int j = 0; j < m; ++j) {
            if (i1 % 2 == 1) {
                pos.push_back(j);
            }
            i1 /= 2;
        }
        if (pos.size() < mx) {
            continue;
        }
        for (int j = 1; j < (1 << (pos.size())); ++j) {
            int k = j;
            for (int l = 0; l < pos.size(); ++l) {
                if (k % 2 == 1) {
                    swap(edge[pos[l]].first, edge[pos[l]].second);
                }
                k /= 2;
            }
            vector<int> co = get(n, m, edge);
            k = j;
            for (int l = 0; l < pos.size(); ++l) {
                if (k % 2 == 1) {
                    swap(edge[pos[l]].first, edge[pos[l]].second);
                }
                k /= 2;
            }
            if (co == col) {
                p = false;
                break;
            }
        }
        if (p) {
            cnt1[pos.size()]++;
            mx = max(mx, (int) pos.size());
        } else {
            int k = (i & ((1 << (m / 2)) - 1));
            for (int j = 0; j < (1 << (m - m / 2)); ++j) {
                if (((i >> (m / 2)) & j) == i) {
                    f[k][j] = true;
                }
            }
        }
    }

    cout << mx << " " << cnt1[mx];
}