// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(69); // chrono::steady_clock::now().time_since_epoch().count()
#define all(x) x.begin(), x.end()
// #define int long long
const int INF = 1e9 + 69;
const int MOD = 1e9 + 7;
const int p = 31;
#define ull unsigned long long
#define ld long double
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

vector<vector<int>> edges_in;

int n, m;

vector<vector<int>> get_hash_comp(vector<pair<int, int>> edges) {
    vector<vector<bool>> can_get_in(n, vector<bool>(n, false));
    edges_in.clear();
    edges_in.assign(n, {});
    for (int i = 0; i < m; i++) {
        edges_in[edges[i].first].push_back(edges[i].second);
    }
    int cur_begin, v;
    for (int v_source = 0; v_source < n; v_source++) {
        vector<int> cur_q = {v_source};
        cur_begin = 0;
        can_get_in[v_source][v_source] = true;
        while (cur_begin < (int)cur_q.size()) {
            v = cur_q[cur_begin];
            for (auto u : edges_in[v]) {
                if (!can_get_in[v_source][u]) {
                    can_get_in[v_source][u] = true;
                    cur_q.push_back(u);
                }
            }
            cur_begin++;
        }
    }
    vector<bool> is_used(n, false);
    vector<vector<int>> ans = {};
    for (int i = 0; i < n; i++) {
        if (is_used[i]) {
            continue;
        }
        vector<int> cur_storng = {};
        for (int j = i; j < n; j++) {
            if (can_get_in[i][j] && can_get_in[j][i]) {
                cur_storng.push_back(j);
            }
        }
        ans.push_back({});
        for (auto num : cur_storng) {
            ans[ans.size() - 1].push_back(num);
            is_used[num] = true;
        }
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    int g, ans, ans_pos;
    cin >> n >> m >> g;
    vector<pair<int, int>> edges_source(m);
    for (int i = 0; i < m; i++) {
        cin >> edges_source[i].first >> edges_source[i].second;
        edges_source[i].first--;
        edges_source[i].second--;
    }
    vector<bool> is_pos((1 << m), true);
    vector<vector<int>> hash_source = get_hash_comp(edges_source);
    for (int mask = 1; mask < (1 << m); mask++) {
        if (!is_pos[mask]) {
            continue;
        }
        vector<pair<int, int>> cur_edges = edges_source;
        for (int i = 0; i < m; i++) {
            if (((mask >> i) & 1) == 1) {
                swap(cur_edges[i].first, cur_edges[i].second);
            }
        }
        if (get_hash_comp(cur_edges) == hash_source) {
            is_pos[mask] = false;
            vector<int> cur_zero = {};
            for (int i = 0; i < m; i++) {
                if (((mask >> i) & 1) == 0) {
                    cur_zero.push_back(i);
                }
            }
            for (int j = 0; j < (int)cur_zero.size(); j++) {
                is_pos[mask | (1 << cur_zero[j])] = false;
            }
        }
    }
    ans = 0;
    ans_pos = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        vector<int> cur_zero = {};
        for (int i = 0; i < m; i++) {
            if (((mask >> i) & 1) == 0) {
                cur_zero.push_back(i);
            }
        }
        if (is_pos[mask]) {
            int cur_num_one = m - (int)cur_zero.size();
            if (cur_num_one > ans) {
                ans = cur_num_one;
                ans_pos = 0;
            }
            if (ans == cur_num_one) {
                ans_pos++;
            }
        } else {
            for (int j = 0; j < (int)cur_zero.size(); j++) {
                is_pos[mask | (1 << cur_zero[j])] = false;
            }
        }
    }
    cout << ans << "\n" << ans_pos << endl;
    return 0;
}
// test
