UVa 11503 - Virtual Friends

// Accepted

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef unsigned long long ull;
typedef map<string, int>mpsi;

const int mod = 1000007;
const int high = 100003;

int par[high] , num[high];

int findd(int n)
{
    return par[n] == n ? n : (par[n] = findd(par[n]));
}

int unionn(int a , int b)
{
    int u = findd(a);
    int v = findd(b);

    if(u == v) return num[u];
    else
    {
        if(num[u] > num[v])
        {
            num[u] += num[v];

            par[v] = u;

            return num[u];
        }

        num[v] += num[u];
        par[u] = v;
        return num[v];
    }
}

char fst[35] , snd[35];

int main()
{
    int t , n , i , ans , sz=0;
    mpsi mp;

    sf("%d", &t);

    while(t--)
    {
        mp.clear();

        sf("%d", &n);

        sz=0;

        while(n--)
        {
            sf("%s %s", &fst , &snd);

            if(!mp.count(fst))
            {
                sz++;

                mp[fst] = sz;

                par[sz] = sz;

                num[sz] = 1;
            }

            if(!mp.count(snd))
            {
                sz++;

                mp[snd] = sz;

                par[sz] = sz;

                num[sz] = 1;
            }

            ans = unionn(mp[fst] , mp[snd]);

            pf("%d\n" , ans);
        }
    }

    return 0;
}