Friend Network

Interview

Time limit3sMemory limit256 MB

Summary
Process friendships one by one and after each union print the size of the merged friend network containing the two users.
Level

Medium6 of 10

Topics
Union-find, Hash map, Implementation
Solved
No attempts yet

Problem

Minhyuk loves making friends on social networking sites. Just as some people collect stamps, Minhyuk's hobby is collecting friends on social networks.

You are given the friendships of a site in the order they are formed. Each time a new friendship is formed, determine how many people belong to the friend network that contains the two people in that friendship.

A friend network is the set of people who can reach one another by moving only along friendships. In other words, two people belong to the same friend network if one can be reached from the other through a chain of friendships (a friend, a friend of a friend, and so on), even if they are not direct friends.

Input

The first line contains the number of test cases. The first line of each test case contains the number of friendships FF, which is at most 100,000. Each of the following FF lines contains one friendship, in the order the friendships are formed. A friendship consists of the IDs of two users; each ID is a string of at most 20 characters made up only of uppercase and lowercase English letters.

Output

Each time a friendship is formed, print on its own line the number of people in the friend network that contains the two people in that friendship.

Examples1

  1. Example 1

    Input
    2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty
    Expected output
    2
3
4
2
2
4