import sys
import math
input = sys.stdin.readline
T = int(input())
result = []
for _ in range(T):
K,M,P = map(int, input().split())
graph = [[] for _ in range(M+1)]
strah_n = [0 for _ in range(M+1)]
for _ in range(P):
a,b = map(int, input().split())
graph[b].append(a)
def dfs(u):
global strah_n, graph
if len(graph[u])==0:
strah_n[u] = 1
return 1
else:
parent_n = []
for v in graph[u]:
if strah_n[v] == 0:
strah_n[v] = dfs(v)
parent_n.append(strah_n[v])
strah_n[u] = max(parent_n)
if parent_n.count(strah_n[u]) > 1:
strah_n[u] += 1
return strah_n[u]
for m in range(1,M+1):
if strah_n[m] == 0:
dfs(m)
result.append([K,strah_n[M]])
for K, r in result:
print(K, r)