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:
3
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

Added by:Sharaf
Date:2013-02-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:2013 acmASCIS Level 1 Contest

hide comments
2013-02-23 15:05:18 Aditya Bahuguna
@:D .....still in trance..hw cn sm1 solve this in 0.00s
2013-02-17 02:58:08 (Tjandra Satria Gunawan)(曾毅昆)
@Akhil Rao: in case #2 we should add pair (0,0) [because we have (0,1) and (1,0), but we don't have (0,0)] and (1,1) [because we have (1,0) and (0,1) but we don't have (1,1)]...
2013-02-14 18:10:48 Akhil Rao
can anyone explain me the second test case??
2013-02-13 20:18:08 :D
I may be a little picky, but description says sets, while input seems to have some multisets.

Other than that, it's a nice easy question. Set size could be limited with N*N.

Last edit: 2013-02-13 20:26:16
2013-02-13 15:47:48 abdelkarim
easy one... :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.