#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<vector<ll>> G;

int main()
{
    ll n, m, g, cnt = 0;
    cin >> n >> m >> g;
    G.assign(n, vector<ll>(0));
    for (int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        G[u].push_back(v);
        if (v > u + 1){
            cnt++;
        }
    }
    if (g == 5){
        cout << n - 1 << " " << pow(2, n) << endl;
        return 0;
    }
    cout << cnt << " " << 0 << endl;
    return 0;
}



/*
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, m;
vector<ll> a, b, c, g;

bool solve(int i, vector<int> d){
    //cout << i << ": ";
    //for (int x = 0; x < d.size(); ++x){
        //cout << d[x] << " ";
    //}
    //cout << endl;
    if (i == n){
        return 0;
    }
    vector<int> d1 = d;
    if (g[b[i]] != -1){
        d1[g[b[i]]]++;
    }
    if (d[i] % 2 == 0){
        if (solve(i + 1, d)){
            return 1;
        }
    }
    if (d[i] % 2 == 1){
        if (!solve(i + 1, d)){
            return 1;
        }
    }
    if (d1[i] % 2 == 0){
        if (solve(i + 1, d1)){
            return 1;
        }
    }
    if (d1[i] % 2 == 1){
        if (!solve(i + 1, d1)){
            return 1;
        }
    }
    return 0;
}

int main()
{
    cin >> n >> m;
    a.resize(n);
    b.resize(n);
    c.resize(m);
    g.assign(2 * n + m + 1, -1);
    vector<pair<ll, ll>> ab(n);
    for (int i = 0; i < n; ++i){
        cin >> a[i];
    }
    ll cnt = -1;
    for (int i = 0; i < n; ++i){
        cin >> b[i];
        ab[i] = {a[i], b[i]};
    }
    sort(ab.begin(), ab.end());
    for (int i = 0; i < n; ++i){
        a[i] = ab[i].first;
        b[i] = ab[i].second;
    }
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            if (a[j] < b[i]){
                g[b[i]] = j;
            }
        }
    }
    cnt = -1;
    vector<int> tmp(n);
    bool f = true;
    for (int i = 0; i < m; ++i){
        cin >> c[i];
    }
    sort(c.begin(), c.end());
    for (int i = 0; i < m; ++i){
        while (cnt + 1 < n && c[i] > a[cnt + 1]){
            cnt++;
        }
        if (cnt != -1){
            tmp[cnt]++;
        } else{
            f = !f;
        }
    }
    if (!(solve(0, tmp) ^ f)){
        cout << "First" << endl;
    } else{
        cout << "Second" << endl;
    }
    return 0;
}

*/

