#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx")

using namespace std;
//#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
int inf = 1e9;
int mod = 1e9+7;
int n, m;
vector<vector<int>> g;
vector<vector<int>> cp;
vector<pair<int, int>> e;

void dfs(int v, vector<int> &used, vector<int> &res){
    used[v] = 1;
    res.push_back(v);
    for(int i = 0; i < n; ++i){
        if(g[v][i]){
            if(!used[i]){
                dfs(i, used, res);
            }
        }
    }
}

vector<int> can(int v){
    vector<int> res;
    vector<int> used(n);
    dfs(v, used, res);
    return res;
}

vector<vector<int>> bcp(vector<vector<int>> &g){
    vector<vector<int>> h(n, vector<int> (n));
    for(int i = 0; i < n; ++i){
        vector<int> cn = can(i);
        for(auto x : cn){
            h[i][x] = 1;
        }
    }
    vector<int> used(n);
    vector<vector<int>> ans;
    for(int i=0 ; i < n; ++i){
        if(!used[i]){
            ans.push_back({});
            for(int j =0 ; j < n; ++j){
                if(!used[j]){
                    if(h[i][j] && h[j][i]){
                        ans.back().push_back(j);
                        used[j] = 1;
                    }
                }
            }
            sort(all(ans.back()));
        }
    }
    sort(all(ans));
    return ans;
}
bool check(vector<int> &c){
    vector<int> pup;
    for(int i = 0; i < m; ++i){
        if(c[i]){
            pup.push_back(i);
        }
    }
    bool ans =1;
    int l = (1 << (int)pup.size());
    for(int mask = 1; mask < l; ++mask){
        for(int i = 0; i < pup.size(); ++i){
            if((mask >> i) & 1){
                int x = pup[i];
                swap(g[e[x].first][e[x].second], g[e[x].second][e[x].first]);
            }
        }
        if(bcp(g) == cp){
            ans = 0;
        }
        for(int i = 0; i < pup.size(); ++i){
            if((mask >> i) & 1){
                int x = pup[i];
                swap(g[e[x].first][e[x].second], g[e[x].second][e[x].first]);
            }
        }
    }
    return ans;
}

void solve() {
    cin >> n >> m;
    int gr;
    cin >> gr;
    g.assign(n, vector<int> (n));
    pair<int, int> mx;
    for(int i= 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u][v] = 1;
        e.push_back({u, v});
    }
    cout << n/2 << " " << 2;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
        solve();
        //cout << '\n';
    }
    return 0;
}
