Lucy has made too many friends but she does not know how many friends are in her circle. Assume that every relation is mutual. If Lucy is Patty's friend, then Patty is also Lucy's friend. Your task is to help Lucy in keeping track of each person's circle size.

Input Specification

The first line of input contains one integer T (T<=10) specifying the number of test cases to follow. Each test case begins with a line containing an integer N (N<=100000), the number of new relations. Each of the following N lines contains couple of strings denoting the names of two people who have just formed relation, separated by a space. Names will have no more than 20 characters.

Output Specification

Print a line containing one integer, the number of people in the combined circle of two people who have just become friends.


Lucy Patty
Patty Alice
Alice Mira
Tiffany Jayden 


2 3 4 2

hide comments
gauravseta: 2017-02-22 12:14:53

I am using Java is getting TLE . tried with ConcurrentHashMap and HashMap both. Someone pls help. using Map correct DS for this problem?
pls help
i am stuck since long
ID: 18821136

Last edit: 2017-02-22 13:35:26
Madhukar Reddy: 2016-08-14 08:44:26

Difficult time limit for slow languages like python

Last edit: 2016-08-14 08:44:45
atif_11: 2016-04-09 20:43:32

time limit is 0.1s - 0.579s but my AC code took time 0.75s in Judge machine. How is it possible?

Last edit: 2016-04-09 20:46:14
thelazycoder: 2016-02-18 19:19:10

Don't know why getting TLE any help please my submission id is 16312319

naruto09: 2016-02-06 09:21:12

very beautiful problem..;) those getting tle in c++ .. try using unordered map instead of map..

Liquid_Science: 2016-02-04 16:57:04

Java coder leave this, do FOXLINGS instead, this need somee serious IO optimizations.

AHH! done , works with bufferedreader with a optimized enough logic!

Last edit: 2016-02-24 05:37:02
xpshekhar: 2016-01-03 02:12:23

Lucy Patty
Patty Alice
Alice Mira
Tiffany Jayden
Jayden Morris
Morris Lucy
Lucy Tiffany

what is the output??

prakhar: 2015-12-07 17:14:18

not a big fan of such questions as it required fast input optimization due to which i wasted lots of time

sailemaverit: 2015-11-06 22:22:11

Time restrictions are too strict for Java users. Please correct.

sailemaverit: 2015-11-05 14:48:08

Really not able to do it with Java! TLE! :/
Even with BufferedInputStream.

Added by:Vamos
Time limit:0.100s-0.579s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64