Java is preferable, but you can choose your suitable programming language.

Winter is not yet over! On some days, the weather can get very cold and often students prefer to travel between university campus buildings via tunnels and bridges. The campus buildings have been gradually connected via various tunnels and bridges. Sometimes these connections are built when the building is built, but it may also be possible to add them afterwards. Unfortunately, sometimes it is not possible to travel between two buildings without going outside because the system of bridges and tunnels is not complete. Your goal is to write a program to help a freshman determine how many buildings can be reached from a newly constructed tunnel. Input The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer n, the total number of bridges or tunnels built. This number will be no more than 105. We assume that all of the buildings have been built ahead of time, but at the beginning of a test case, no bridges or tunnels have been built yet. The rest of the test case consists of n lines giving the history of the bridges or tunnels, in the order in which they are built. Each of these lines contains the names of the two buildings being connected, separated by a space. Each building name is a sequence of up to 20 uppercase or lowercase letters, and building names are case-sensitive. Output Whenever a bridge or tunnel is built, print a line containing one integer, the number of buildings that can be reached from that bridge without going outside. Hint: study how to implement Kruskal's algorithm using disjoint-set data structure. Sample Input 1 3 EV HH HH MB EV ERBuild Sample Output 2 3 4