친구 네트워크

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아합니다. 우표를 모으는 취미가 있는 사람처럼, 민혁이는 소셜 네트워크에서 친구를 모으는 것이 취미입니다.

어떤 사이트에서 친구 관계가 만들어진 순서대로 주어집니다. 친구 관계가 하나씩 생길 때마다, 그 관계에 등장한 두 사람이 속한 친구 네트워크에 몇 명이 있는지 구하세요.

친구 네트워크란 친구 관계를 따라서만 이동해도 서로 오갈 수 있는 사람들의 집합을 말합니다. 즉, 두 사람이 직접 친구가 아니어도 친구의 친구, 친구의 친구의 친구처럼 관계를 이어 도달할 수 있으면 같은 친구 네트워크에 속합니다.

첫째 줄에 테스트 케이스의 개수가 주어집니다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 $F$가 주어지며, $F$는 100,000을 넘지 않습니다. 이어지는 $F$개의 줄에는 친구 관계가 만들어진 순서대로 하나씩 주어집니다. 각 친구 관계는 두 사용자의 아이디로 이루어지며, 아이디는 알파벳 대문자와 소문자로만 이루어진 길이 20 이하의 문자열입니다.

각 친구 관계가 만들어질 때마다 한 줄에, 그 관계에 등장한 두 사람이 속한 친구 네트워크에 있는 사람의 수를 출력합니다.