[백준] 친구 네트워크.py

test_case = int(input())
def parent_find(x):
    if x == parent[x]:
        return x
    else:
        p = parent_find(parent[x])
        parent[x] = p
        return parent[x]
    
# x가 y의 parent인 것으로 전제한다.    
def union(x, y):
    x = parent_find(x)
    y = parent_find(y)
    # 두 사람이 친구관계가 아닌 경우 연결해 준다.
    # y의 parent로 x를 연결하고, 
    # x의 친구관계 숫자에 y가 가지고 있던 친구 수를 더해 준다
    if x != y:
        parent[y] = x
        number[x] += number[y]

for _ in range(test_case):
    n = int(input())
    parent, number = dict(), dict()
    for _ in range(n):
        x, y = input().split()
        if x not in parent:
            parent[x] = x
            number[x] = 1
        if y not in parent:
            parent[y] = y
            number[y] = 1
        union(x,y)
        print(number[parent_find(x)])