#include <iostream>
#include <random>
#include <numeric>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr int maxn = 2010;

int n, m, group;
vector<pair<int, int>> g[maxn];
int in_cnt[maxn], out_cnt[maxn];
int dists[maxn];
bool need[maxn];

void dfs(int v, int d) {
    dists[v] = d;
    for (auto [u, eid]: g[v]) if (dists[u] < d + 1) dfs(u, d + 1);
}

void dfs2(int v) {
    for (auto [u, eid]: g[v]) {
        if (dists[u] != dists[v] + 1) continue;
        need[eid] = true;
        dfs2(u);
    }
}

void solve() {
    cin >> n >> m >> group;
    set<int> ss;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v, --u, --v;
        g[u].emplace_back(v, i);
        ++out_cnt[u], ++in_cnt[v];
        if (u + 1 != v && u - n + 1 != u) {
            ss.insert(u);
            ss.insert(v);
        }
    }
    cout << n+1 << "\n";
    cout << "1\n";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t = 1;
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> t;
#else
#ifdef TEST
    freopen("input.txt", "r", stdin);
#else
#endif
#endif
    while (t--) {
        solve();
        cout << "\n";
    }
    return 0;
}

//    for (int i = 0; i < n; ++i) {
//        for (int j = 0; j < n; ++j) dists[j] = 0;
//        dfs(i, 0);
//        dfs2(i);
//    }
//    int cnt = 0;
//    for (int i = 0; i < m; ++i) cnt += need[i];
//    cout << 0 << "\n";