Baekjoon-9470-Strahler 순서

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)