[백준] 자바 문제 풀이 4195 : 골드2

import java.util.*;
import java.io.*;


public class Main {
    static int num = 0;
    static Map<String, Integer> name = new HashMap<>();
    static int[] parent;
    static int[] count;


    public static boolean union(int x, int y) {
        x = find(x);
        y = find(y);


        if(x == y) return false;

        if(x <= y) {
            parent[y] = x;
            count[x] = count[y] + count[x];
        }
        else {
            parent[x] = y;
            count[y] = count[y] + count[x];
        }

        return true;
    }

    public static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int test_case = Integer.parseInt(br.readLine());

        for(int t = 0; t < test_case; t++) {
            int n = Integer.parseInt(br.readLine());
            parent = new int[200000];
            count = new int[200000];
            name.clear();

            for(int i = 0; i < n; i++) {
                String[] s = br.readLine().split(" ");

                if(name.get(s[0]) == null) {
                    name.put(s[0], num++);
                    parent[name.get(s[0])] = name.get(s[0]);
                    count[name.get(s[0])] = 1;
                }

                if(name.get(s[1]) == null) {
                    name.put(s[1], num++);
                    parent[name.get(s[1])] = name.get(s[1]);
                    count[name.get(s[1])] = 1;
                }

                union(name.get(s[0]), name.get(s[1]));

                bw.write(count[find(name.get(s[0]))] + "\n");
                bw.flush();
            }
        }
        br.close();
        bw.close();
    }
}