// Arup Guha
// 2/22/2014
// Solution to 2013 Greater NY Regional Problem C: Strahler Order

import java.util.*;

public class c {

	final public static int UNFILLED = -1;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Go through each case.
		for (int loop=1; loop<=numCases; loop++) {

			// Read in data.
			int caseNum = stdin.nextInt();
			int v = stdin.nextInt();
			int e = stdin.nextInt();

			int[][] eList = new int[e][2];
			int[] inDeg = new int[v];
			boolean[] hasOut = new boolean[v];
			for (int i=0; i<e; i++) {
				eList[i][0] = stdin.nextInt()-1;
				eList[i][1] = stdin.nextInt()-1;
				inDeg[eList[i][1]]++;
				hasOut[eList[i][0]] = true;
			}

			// Allocate space for in list.
			int[][] inList = new int[v][];
			for (int i=0; i<v; i++)
				inList[i] = new int[inDeg[i]];

			// Form in list.
			int[] inIndex = new int[v];
			for (int i=0; i<e; i++) {
				int in = eList[i][1];
				int out = eList[i][0];
				inList[in][inIndex[in]++] = out;
			}

			// Store all answers here.
			int[] order = new int[v];
			Arrays.fill(order, UNFILLED);

			// Find mouth.
			int mouth = -1;
			for (int i=0; i<v; i++)
				if (!hasOut[i])
					mouth = i;

			// Output solution.
			System.out.println(loop+" "+solve(inList, mouth, order));
		}
	}

	public static int solve(int[][] inList, int v, int[] memo) {

		// Easy cases.
		if (memo[v] != UNFILLED) return memo[v];
		if (inList[v].length == 0) return 1;

		// Store our best one and the best with frequency 2.
		int bestTwo = 0, bestOne = 0;
		HashSet<Integer> seen = new HashSet<Integer>();
		for (int i=0; i<inList[v].length; i++) {

			// Solve this neighbor node.
			int next = solve(inList, inList[v][i], memo);
			if (seen.contains(next)) {

				// Update seen best seen twice.
				if (next > bestTwo)
					bestTwo = next;
			}
			else
				seen.add(next);

			// Update best seen.
			if (next > bestOne) bestOne = next;
		}

		// Store and return.
		memo[v] = Math.max(bestOne, bestTwo+1);
		return memo[v];
	}
}