// #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;
vector<vector<int>> edges_out;

int n, m;

vector<int> top_sort = {};
vector<bool> used;
vector<int> color;
vector<int> min_v;
int cur_color = -1;

void dfs1(int v) {
    used[v] = true;
    for (auto u : edges_in[v]) {
        if (!used[u]) {
            dfs1(u);
        }
    }
    top_sort.push_back(v);
}

void dfs2(int v) {
    color[v] = cur_color;
    min_v[cur_color] = min(min_v[cur_color], v);
    for (auto u : edges_out[v]) {
        if (color[u] == -1) {
            dfs2(u);
        }
    }
}

vector<int> get_hash_comp(vector<pair<int, int>> edges) {
    edges_in.clear();
    edges_in.assign(n, {});
    edges_out.clear();
    edges_out.assign(n, {});
    for (int i = 0; i < m; i++) {
        edges_in[edges[i].first].push_back(edges[i].second);
        edges_out[edges[i].second].push_back(edges[i].first);
    }
    top_sort.clear();
    used.assign(n, false);
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs1(i);
        }
    }
    color.assign(n, -1);
    cur_color = -1;
    reverse(all(top_sort));
    min_v.assign(n, n);
    for (auto v : top_sort) {
        if (color[v] == -1) {
            cur_color++;
            min_v[cur_color] = v;
            dfs2(v);
        }
    }
    for (int i = 0; i < n; i++) {
        color[i] = min_v[color[i]];
    }
    return color;
}

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<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
