#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <array>
using namespace std;
typedef long long ll;
const ll Inf = 1e16;
const ll mod = 1e9+7;
vector<vector<ll>>g;
vector<ll>euler; vector<ll>used;
vector<vector<ll>>ag;
void dfs(ll v) {
    used[v] = 1;
    for (auto u:g[v]) {
        if (used[u])continue;
        dfs(u);
    }
    euler.push_back(v);
}
vector<ll>c; ll cnt = 0;
void color(ll v) {
    c[v] = cnt; used[v] = 1;
    for (auto x : ag[v]) {
        if (!used[x])color(x);
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    ll n, m, G; cin >> n >> m >> G;
    vector<vector<ll>>in(n);
    vector<vector<ll>>out(n);
    vector<pair<ll, ll>>E;
    for (int i = 0; i < m; i++) {
        ll u, v; cin >> u >> v; u--; v--;
        out[u].push_back(i);
        in[v].push_back(i);
    }
    /*ag.resize(m); g.resize(m); c.resize(m);
    for (int i = 0; i < n; i++) {
        if (in[i].size() == 1) {
            for (auto x : out[i]) {
                g[x].push_back(in[i][0]);
                E.push_back({ x, in[i][0] });
                ag[in[i][0]].push_back(x);
            }
        }
        if (out[i].size() == 1) {
            for (auto x : in[i]) {
                g[x].push_back(out[i][0]);
                E.push_back({ x, out[i][0] });
                ag[out[i][0]].push_back(x);
            }
        }
    }
    used.resize(m);
    for (int i = 0; i < m; i++) {
        if (!used[i])dfs(i);
    }
    reverse(euler.begin(), euler.end());
    used = vector<ll>(m, 0);
    vector<ll>sz;
    for (int i = 0; i < m; i++) {
        if (used[euler[i]]) {
            sz[c[euler[i]]]++; continue;
        }
        color(euler[i]); cnt++; sz.push_back(1);
    }
    vector<ll>istok(cnt, 1);
    for (auto [u, v] : E) {
        if (c[u] != c[v])
            istok[c[v]] = 0;
    }
    ll count = 1, ans = 0;
    for (int i = 0; i < cnt; i++) {
        if (istok[i]) {
            ans++; count *= sz[i];
            count %= mod;
        }
    }*/
    cout << m << " 1";
}
/*6 8 0
2 1 
3 2
4 3
5 4
6 5
1 6
1 5
5 2

3 3 0
1 2
2 3 
3 1

7 10 0
1 2
2 3
3 4
4 5
5 2
2 6
6 7
7 1
6 1
3 1

5 7 0
1 2 
2 3 
3 4 
4 5 
5 1 
3 2 
5 3*/