#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <unordered_map>
#include <random>

#define all(v) v.begin(), v.end()
#define len(v) (int)v.size()
#define coutd cout << fixed << setprecision(20)

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

const ll Mod = 1e9 + 7;

vector<vector<int>> g;
vector<vector<int>> rg;

int mx = 0, mxcnt = 1;
int n, m;
vector<vector<int>> ng;
vector<vector<int>> rng;
vector<int> ts;
vector<bool> used;
vector<int> col;
vector<int> stcol;
vector<int> dp;
/*vector<pair<int, int>> edges;

map<ll, int> mp;

void setid(int v, int u, int id)
{
    if (v > u) swap(v, u);
    mp[v * n + u] = id;
}

int getid(int v, int u)
{
    if (v > u) swap(v, u);
    return mp[v * n + u];
}*/

void dfsts(int v)
{
    used[v] = 1;
    for (int u : ng[v])
    {
        if (!used[u])
        {
            dfsts(u);
        }
    }
    ts.push_back(v);
}

void dfscol(int v, int c)
{
    col[v] = c;
    for (int u : rng[v])
    {
        if (!col[u])
        {
            dfscol(u, c);
        }
    }
}

void dfsstcol(int v, int c)
{
    stcol[v] = c;
    for (int u : rng[v])
    {
        if (!stcol[u])
        {
            dfsstcol(u, c);
        }
    }
}

void make(int pos, vector<int> &arr)
{
    if (pos == m)
    {
        int cur = 0;
        int ecnt = 0;
        ng.assign(n, {});
        rng.assign(n, {});
        int msk = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j : g[i])
            {
                if (arr[ecnt] == 0)
                {
                    ng[i].push_back(j);
                    rng[j].push_back(i);
                }
                if (arr[ecnt] == 1)
                {
                    msk += (1 << ecnt);
                    ng[i].push_back(j);
                    rng[j].push_back(i);
                } else if (arr[ecnt] == 2)
                {
                    msk += (1 << ecnt);
                    ng[j].push_back(i);
                    rng[i].push_back(j);
                }
                ++ecnt;
            }
        }
        used.assign(n, 0);
        col.assign(n, 0);
        ts.clear();
        for (int i = 0; i < n; ++i)
        {
            if (!used[i])
            {
                dfsts(i);
            }
        }
        reverse(all(ts));
        vector<bool> colused(n, 0);
        for (int v : ts)
        {
            if (!col[v])
            {
                if (colused[stcol[v]])
                {
                    return;
                }
                dfscol(v, stcol[v]);
                colused[stcol[v]] = 1;
            }
        }
        for (int i = 0; i < n; ++i)
        {
            if (stcol[i] != col[i]) return;
        }
        dp[msk] += 1;
        return;
    }
    for (int i = 0; i < 3; ++i)
    {
        arr[pos] = i;
        make(pos + 1, arr);
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int group;
    cin >> n >> m >> group;
    g.resize(n);
    rg.resize(n);
    dp.resize(1 << m, 0);
    for (int i = 0; i < m; ++i)
    {
        int v, u;
        cin >> v >> u;
        --v;
        --u;
        //setid(v, u, len(edges));
        //edges.push_back({v, u});
        g[v].push_back(u);
        rg[u].push_back(v);
    }
    ng = g;
    rng = rg;
    used.assign(n, 0);
    stcol.assign(n, 0);
    ts.clear();
    for (int i = 0; i < n; ++i)
    {
        if (!used[i])
        {
            dfsts(i);
        }
    }
    reverse(all(ts));
    int num = 1;
    for (int v : ts)
    {
        if (!stcol[v])
        {
            dfsstcol(v, num++);
        }
    }
    vector<int> arr(m);
    make(0, arr);
    for (int i = 0; i < (1 << m); ++i)
    {
        if (dp[i] == 1)
        {
            int cnt = 0;
            for (int j = 0; j < m; ++j)
            {
                cnt += ((i >> j) & 1);
            }
            if (mx < cnt)
            {
                mx = cnt;
                mxcnt = 1;
            } else if (mx == cnt)
            {
                ++mxcnt;
            }
        }
    }
    cout << mx << ' ' << -1;

    return 0;
}
