This weekend, the long-awaited BIT (Boomerang Invitational Tournament) will be taking place! N of the finest boomerangists will be competing in a randomly-seeded single-elimination bracket.
For those unfamiliar with this tournament format, the process can be modelled as follows:
The N competitors are arranged in a queue (an ordered list), in some order
If the queue currently contains only 1 competitor, the tournament ends with them as the champion
Otherwise, the first 2 competitors in the front of the queue are removed, and they play a match against one another
The winner of that match is re-inserted into the queue, at the back
Repeat from step 2
The one-on-one matches in this tournament are, of course, boomerang duels to the death. If the ith and jth competitors face off against one another, the ith competitor will win if Wi,j = 1. Otherwise, if Wi,j = 0, the jth competitor will win. Note that, for all (1 ≤ i, j ≤ N), Wi,j = 0 or 1, and Wi,i = 0 (no one will play against themselves anyway), and Wi,j ≠ Wj,i (if i ≠ j). Those are the only constraints. It's possible that, for example, competitor A can beat B, B can beat C, and C can beat A.
Once the tournament is over, each boomerangist is given a placing (even if they didn't survive the competition). A given competitor c's placing is an integer one greater than the number of competitors who won strictly more matches than c did.
For each boomerangist, you'd like to know both the best (smallest) and the worst (largest) placing they could possibly end up with, given that the initial ordering of the competitors (in step 1 of the tournament) is unknown.
Input
Input begins with an integer T, the number of tournaments. For each tournament, there is first a line containing the integer N. Then follow N lines, the ith of which contains the space-separated integers Wi,1 through Wi,N.
Output
For the ith tournament, print a line containing "Case #i: " followed by N lines that each contain two space-separated integers. The first integer on the ith line should be the best possible placing for the ith competitor, and the second should be the worst possible placing.
Constraints
1 ≤ T ≤ 250
N = 2K where K is an integer and 0 ≤ K ≤ 4
Explanation of Sample
In the second tournament, the first competitor will always beat the second competitor, so the first competitor will finish in 1st place, and the other in 2nd place. In the third tournament, the first competitor never loses, so they will finish in 1st place. The fourth competitor never wins, so they will finish tied for 3rd place with the other competitor who loses their initial match. The other two competitors will either lose their first match (if initially paired with the first competitor) or their second match (if initially paired with the fourth competitor), so they can each finish in 2nd place, or tied for 3rd place.
Sample input
Code: Select all
5
1
0
2
0 1
0 0
4
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
4
0 0 0 0
1 0 0 1
1 1 0 0
1 0 1 0
8
0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
1 1 1 0 0 1 1 0
1 1 1 1 0 1 0 1
1 1 1 0 0 0 0 1
1 1 1 0 1 1 0 1
1 1 1 1 0 0 0 0Code: Select all
Case #1:
1 1
Case #2:
1 1
2 2
Case #3:
1 1
2 3
2 3
3 3
Case #4:
3 3
1 3
1 3
1 3
Case #5:
5 5
3 5
3 5
1 5
1 5
2 5
1 5
1 5