#include<bits/stdc++.h>
using namespace std;

typedef long double ld;

vector<vector<int>> ins(1005);
// vector<vector<int>> outs(1005);
int order[1005];

int get_order(int a) {
    if(order[a] < 1e9) return order[a];
    if(ins[a].size() == 0) {
        order[a] = 1;
        return 1;
    }

    map<int,int> m;
    for(int b : ins[a]) m[get_order(b)]++;

    pair<int,int> c = *(--m.end());
    // cout << "HI " << a << ' ' << c.first << ' ' << c.second << '\n';
    if(c.second == 1) order[a] = c.first;
    else order[a] = c.first + 1;
    return order[a];

}

void solve() {

    int K, N, M;
    cin >> K >> N >> M;
    int A, B;

    for(int i=0;i<M;i++) {
        cin >> A >> B;
        A--;
        B--;

        // outs[A].push_back(B);
        ins[B].push_back(A);
    }

    for(int i=0;i<N;i++) order[i] = 1e9;
    cout << K << ' ' << get_order(N-1) << '\n';
    // for(int i=0;i<N;i++) cout << order[i] << ' ';
    // cout << '\n';


    for(int i=0;i<N;i++) {
        ins[i].clear();
        // outs[i].clear();
        order[i] = 0;
    }


    return;

}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(2);

    int P;
    cin >> P;
    for(int i=0;i<P;i++) solve();

    return 0;
}