// 1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <immintrin.h>
#include <set>
#include <map>
#include <numeric>
#include <queue>

using ll = long long;
using ld = long double;
using namespace std;

struct independant_graph
{
    vector<vector<int>> g, ug;
    vector<bool> used;
    vector<int>c, topsort;
    void dfs1(int v)
    {
        if (used[v])
            return;
        used[v] = 1;
        for (auto& u : ug[v])
        {
            dfs1(u);
        }
        topsort.push_back(v);
    }
    void dfs2(int v, int cv)
    {
        if (c[v] == cv)
            return;
        if (c[v] != -1)
            return;
        c[v] = cv;
        for (auto& u : g[v])
        {
            dfs2(u, cv);
        }
    }
};

vector <int> independant_colorizing(int n, vector <pair<int, int>> edges)
{
    independant_graph ig;
    ig.g.resize(n);
    ig.ug.resize(n);
    ig.used.assign(n, false);
    ig.c.assign(n, -1);
    for (auto& i : edges)
    {
        ig.g[i.first].push_back(i.second);
        ig.ug[i.second].push_back(i.first);
    }
    for (size_t i = 0; i < n; i++)
    {
        if (ig.used[i])
            continue;
        ig.dfs1(i);
    }
    int cv = 0;
    reverse(ig.topsort.begin(), ig.topsort.end());
    for (auto& i : ig.topsort)
    {
        if (ig.c[i] == -1)
        {
            ig.dfs2(i, cv++);
        }
    }
    vector <pair<int,int>> mn(cv);
    for (size_t i = 0; i < cv; i++)
    {
        mn[i].second = i;
    }
    for (size_t i = 0; i < n; i++)
    {
        mn[ig.c[i]].first = i;
    }
    sort(mn.begin(), mn.end());
    vector <int> trans(cv);
    for (size_t i = 0; i < cv; i++)
    {
        trans[mn[i].second] = i;
    }
    for (auto& i : ig.c)
    {
        i = trans[i];
    }
    return ig.c;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, g;
    cin >> n >> m >> g;
    vector <pair<int, int>> orig(m);
    for (auto& i : orig)
    {
        cin >> i.first >> i.second;
        i.first--;
        i.second--;
    }
    vector <bool>can(1 << m, true);
    auto bs = independant_colorizing(n, orig);
    for (size_t i = 1; i < (1 << m); i++)
    {
        for (size_t j = 0; j < m; j++)
        {
            if ((i >> j) & 1)
            {
                swap(orig[j].first, orig[j].second);
            }
        }
        if (bs == independant_colorizing(n, orig))
        {
            can[i] = false;
        }
        for (size_t j = 0; j < m; j++)
        {
            if ((i >> j) & 1)
            {
                swap(orig[j].first, orig[j].second);
            }
        }
    }
    for (size_t i = 0; i < (1 << m); i++)
    {
        for (size_t j = 0; j < m; j++)
        {
            if ((i >> j) & 1)
            {
                if (!can[i ^ (1 << j)])
                {
                    can[i] = false;
                    break;
                }
            }
        }
    }
    int ans = 0, best = 0;
    for (size_t i = 0; i < (1 << m); i++)
    {
        if (can[i])
        {
            int c = 0;
            for (size_t j = 0; j < m; j++)
                if ((i >> j) & 1)
                    c++;
            if (best == c)
                ans++;
            if (best < c)
                best = c, ans = 1;
        }
    }
    cout << best << '\n' << ans << '\n';
    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
