TRANCLS  Transitive Closure
In mathematics, a set S is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c. In other words, any set of pairs is transitive if and only if you have (a,b) and (b,c) then you also must have (a,c). Check this example: S = { (1,2),(2,3),(3,4),(2,4) }. Is set S is transitive relation ? No, Because you have (1,2) and (2,3) but you don’t have (1,3) If we add (1,3) will it be transitive ? (( S = { (1,2),(2,3),(3,4),(2,4),(1,3) } )) No, Because you have (1,3) and (3,4) but you don’t have (1,4) If we add (1,4) will it be transitive ? (( S = { (1, 2),(2,3),(3,4),(2,4),(1,3),(1,4) } )) Yes, Now the set S is now transitive after we added 2 pairs { (1,3),(1,4) } These pairs called transitive closure (which means the minimal pairs that convert set S into a transitive set ). Your task is given the set S you have to output the minimal pairs have to be added to make the set S transitive.
Input
The first line of input is the number of test cases T where (0<T<=100), Each test case you'll be given the number of pairs in the set N where (0<N<=100), followed by N pairs (a, b) where (0<=a,b<N).
Output
For each test case print "Case_#i:_X" where "i" is the case number, "X" is the minimal number of pairs have to be added to make the set transitive and "_" is a white space. Each test case should be in a separate line.
Example
Input:341 22 32 421 22 11 23 4 0 1 1 2 2 3 1 3 2 0 1 1 0 1 0 0 Output:
Case #1: 2
Case #2: 2
Case #3: 0
hide comments
bphc555:
20190216 19:11:33
Last edit: 20190216 19:11:42 

Pratik Nagelia:
20150622 15:44:29
Beware. Same input pairs can appear multiple times. 

Mayank Ladia:
20150417 21:40:33
Any tricky case pls..


humble_coder:
20141010 07:31:17
I dont understand why I am getting wrong answer.. Isn't this just an easy implementation of floyd warshall with O(n^2) space but getting WA.. 

you_know_why:
20140613 12:29:03
nice.......


Kevin Sebastian:
20130627 17:51:33
pls tell me where i am wrong submission id 9563433 

vishal chaudhary:
20130608 19:02:00
very nice problem..costed me 2 WA due to a silly mistake..:P Last edit: 20130608 19:03:07 

Ouditchya Sinha:
20130607 16:39:25
Finally AC! Quite an easy one. :) 

Vipul Pandey:
20130508 07:28:54
easy! 

arijit pande:
20130507 09:59:19
Made plenty of stupid mistakes, but finally AC. :) 
Added by:  Sharaf 
Date:  20130207 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  2013 acmASCIS Level 1 Contest 