1. 

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #11503 Virtual Friends
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2498
*
* @author Schirm , Mathauser , Mohr

* @version 1.0, 06/29/2009
*
* Status : Accepted
* Runtime: 7.624
*/

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int testcases = sc.nextInt();
int friendships;
String line;

while (testcases > 0) {
testcases--;
line = sc.nextLine();
int count = 0;
HashMap<String, Integer> map = new HashMap<String, Integer>();
ArrayList<Integer> array = new ArrayList<Integer>();
;

// Leerzeilen rausfiltern
while (line.isEmpty())
line = sc.nextLine();

friendships = Integer.parseInt(line);

for (int i = 0; i < friendships; i++) {
line = sc.nextLine();

// Leerzeilen rausfiltern
while (line.isEmpty())
line = sc.nextLine();

String[] tmp = line.split(" ");

// Einer der beiden ist bereits vorhanden
if (map.containsKey(tmp[0]) && !map.containsKey(tmp[1])) {
int num0 = map.get(tmp[0]);
map.put(tmp[1], num0);
array.set(num0, array.get(num0) + 1);
} else if (!map.containsKey(tmp[0]) && map.containsKey(tmp[1])) {
int num1 = map.get(tmp[1]);
map.put(tmp[0], num1);
array.set(num1, array.get(num1) + 1);
}

// Beide sind bereits enthalten
else if (map.containsKey(tmp[0]) && map.containsKey(tmp[1])) {
Iterator<String> iterator = map.keySet().iterator();
int num0 = map.get(tmp[0]);
int num1 = map.get(tmp[1]);
if (num0 != num1) {
array.set(num0, array.get(num0) + array.get(num1));
while (iterator.hasNext()) {
String name = iterator.next();
if (map.get(name) == num1)
map.put(name, num0);
}
}
}

// Neue Freundschaft erstellen
else {
if (tmp[0].equals(tmp[1])) {
map.put(tmp[0], count);
array.add(1);
} else {
map.put(tmp[0], count);
map.put(tmp[1], count);
array.add(2);

}
count++;
}

// Anzahl der Freunde ausgeben
System.out.println(array.get(map.get(tmp[0])));
}

// map löschen
map.clear();
array.clear();
}
}
}