#include <bits/stdc++.h>

using namespace std;

#define ll long long
//#define ld long double
//#define ull unsigned long long
//#define sll __int128
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
//#define int long long

mt19937 rnd(time(0));

ll INF = 1e18;
int mod = 1e9 + 7;

int kv(int x) {
    return ((ll)x * x) % mod;
}

int mult(int a, int b){
    return ((ll)a * b) % mod;
}

int fast_pow(int x, int a){
    if (a == 0) return 1;
    if (a == 1) return x;
    if (a & 1) return mult(x, fast_pow(x, a - 1));
    return kv(fast_pow(x, a / 2));
}

bool rec(set<array<int, 3>> &st1){
    if (st1.empty()){
        return false;
    }
    auto a = *st1.begin();
    st1.erase(st1.begin());
    bool f = rec(st1);
    //st1.insert(a);
    if (a[2] == 1 || !f) return !f;
    swap(a[0], a[1]);
    a[2] = 1;
    st1.insert(a);
    f = rec(st1);
    st1.erase(a);
    swap(a[0], a[1]);
    a[2] = 0;
    st1.insert(a);
    return !f;
    /*
    if (st2.empty() || (*st1.begin())[0] < *st2.begin()){
        auto a = *st1.begin();
        st1.erase(st1.begin());
        bool f1 = rec(st1, st2);
        if (!f1){
            st1.insert(a);
            return true;
        }
        st2.insert(a[1]);
        bool f2 = rec(st1, st2);
        st1.insert(a);
        st2.erase(a[1]);
        return !f2;
    }
    else{
        auto a = *st2.begin();
        st2.erase(a);
        bool f = rec(st1, st2);
        st2.insert(a);
        return !f;
    }
     */
}

void gsrt(int v, vector<bool> &used, vector<vector<int>> &g, vector<int> &ord){
    used[v] = true;
    for (auto to : g[v]){
        if (used[to]) continue;
        gsrt(to, used, g, ord);
    }
    ord.push_back(v);
}

void recol(int v, vector<bool> &used, vector<vector<int>> &g){
    used[v] = true;
    for (auto to : g[v]){
        if (used[to]) continue;
        recol(to, used, g);
    }
}

void solve(){
    int n, m, G;
    cin >> n >> m >> G;
    vector<vector<int>> g(n), gr(n);
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; i++){
        int v, u;
        cin >> v >> u;
        v--; u--;
        edges[i] = {v, u};
        if ((v + 1) % n != u){
            g[v].push_back(u);
            gr[u].push_back(v);
        }
    }
    vector<bool> used(n);
    vector<int> ord;
    for (int i = 0; i < n; i++){
        if (!used[i]){
            gsrt(i, used, g, ord);
        }
    }
    reverse(ord.begin(), ord.end());
    used = vector<bool>(n, false);
    int cnt = 0;
    for (auto v : ord){
        if (!used[v]){
            cnt++;
            recol(v, used, gr);
        }
    }
    cout << cnt << "\n" << 1;
//    int n, m;
//    cin >> n >> m;
//    vector<int> a(n), b(n), c(m);
//    vector<pair<int, int>> d;
//    set<array<int, 3>> st;
//    for (int i = 0; i < n; i++){
//        cin >> a[i];
//    }
//    for (int i = 0; i < n; i++){
//        cin >> b[i];
//        st.insert({a[i], b[i], 0});
//    }
//    for (int i = 0; i < m; i++){
//        cin >> c[i];
//        st.insert({c[i], -1, 1});
//    }
//    sort(all(d));
//    int k = 0;
//    for (int i = size(d) - 1; i > -1; i--){
//        if (d[i].second == 0){
//            k = i % 2;
//            break;
//        }
//    }
//    set<array<int, 3>> st1;
//    set<int> st2;
//    for (int i = 0; i < n; i++){
//        st1.insert({a[i], b[i], 0});
//    }
//    //int d = m % 2;
//    int k = rec(st1);
//    if (rec(st)){
//        cout << "First";
//    }
//    else{
//        cout << "Second";
//    }
}

signed main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ttt = 1;
    //cin >> ttt;
    while (ttt--){
        solve();
    }
}
