UVA 11503

#include <bits/stdc++.h>

using namespace std;

class UF{

public:
    int *a, *sz;
    int n;

    UF(int n){
        sz = new int[n];
        a = new int[n];
        this->n = n;

        for(int i =0 ; i < n; i++)
            a[i] = i, sz[i] = 1;
    }

    int root(int p){
        while(a[p] != p) {
            a[p] = a[a[p]];
            p = a[p];
        }
        return p;
    }

    void merge(int p, int q){
        int i = root(p);
        int j = root(q);

        if(i == j) return;

        if(sz[i] > sz[j]) a[j] = i, sz[i] += sz[j];
        else a[i] = j, sz[j] += sz[i];
    }

    bool find(int p, int q){
        return root(p) == root(q);
    }

};

int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    int t;
    cin >> t;

    while(t-->0){
        int n;
        cin >> n;

        map<string ,int> index;
        int c = 0;
        UF uf(n*2);
        for(int i = 0; i < n; ++i){
            string a,b;
            cin >> a >> b;
            if(!index.count(a))index[a] = c++;
            if(!index.count(b))index[b] = c++;

            uf.merge(index[a], index[b]);

            cout << uf.sz[uf.root(index[a])] << endl;
        }
    }

    return 0;
}