UVa 11503 - Virtual Friends

// UVa 11503 - Virtual Friends
// Disjoint-set forests

#include <iostream>
#include <string>
#include <map>
using namespace std;

int parent[100001], rank[100001];

void MakeSet(int x) {
	parent[x] = x;
	rank[x] = 1;
}

int Find(int x) {
	if (parent[x] != x)
		parent[x] = Find(parent[x]);
	return parent[x];
}

int Union(int x, int y) {
	int xRoot = Find(x);
	int yRoot = Find(y);
	if (xRoot == yRoot)
		return rank[xRoot];
	if (rank[xRoot] < rank[yRoot]) {
		parent[xRoot] = yRoot;
		rank[yRoot] += rank[xRoot];
		return rank[yRoot];
	} else {
		parent[yRoot] = xRoot;
		rank[xRoot] += rank[yRoot];
		return rank[xRoot];
	}
}

int main() {
	int t;
	for (cin >> t; t; t--) {
		int n, m = 0;
		cin >> n;
		map<string, int> id;
		for (int i = 0; i < n; i++) {
			string f1, f2;
			cin >> f1 >> f2;
			if (id[f1] == 0) {
				id[f1] = ++m;
				MakeSet(id[f1]);
			}
			if (id[f2] == 0) {
				id[f2] = ++m;
				MakeSet(id[f2]);
			}
			cout << Union(id[f1], id[f2]) << endl;
		}
	}
	return 0;
}