[그래프] BOJ 4195 친구 네트워크

import sys 
input = sys.stdin.readline 
 
from collections import defaultdict
 
 
def find(parent, x):
    if x != parent[x]:
        parent[x] = find(parent, parent[x])
    return parent[x]
 
def union(parent, parent_cnt, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a != b:
        parent[b] = a
        parent_cnt[a] += parent_cnt[b] 
 
T = int(input())
for _ in range(T):
    F = int(input())
    parent = dict()
    parent_cnt = defaultdict(int)
    for _ in range(F):
        a, b = input().split()
 
        if not parent.get(a): 
            parent[a] = a 
            parent_cnt[a] = 1
        else:
            a = find(parent, a)  
        if not parent.get(b): 
            parent[b] = b
            parent_cnt[b] = 1
        else:
            b = find(parent, b)
 
        union(parent, parent_cnt, a, b)
        print(parent_cnt[a])