[BOJ/백준] 3584 가장 가까운 공통 조상

import sys

input = sys.stdin.readline

T = int(input())

def find_parents(node):
    parent_list = [node]

    while parent_num[node] != -1:
        parent = parent_num[node]
        parent_list.append(parent)
        node = parent

    return parent_list



for _ in range(T):
    N = int(input())
    parent_num = [-1]*(N+1) # 해당 index의 부모가 안에 들어가 있다.
    for _ in range(N-1):
        parent,child = map(int,input().split())
        parent_num[child] = parent


    num1,num2 = map(int,input().split())

    parents1 = find_parents(num1)
    parents2 = find_parents(num2)

    if len(parents1) < len(parents2):
        parents1,parents2 = parents2, parents1
    result = -1
    for num in parents1:
        if num in parents2:
            result = num
            break
    print(result)