1608: Team Builder

You are arranging a weird game for a team building exercise. In this game there are certain locations that people can stand at, and from each location there are paths that lead to other locations, but there are not necessarily paths that lead directly back. You have everything set up, but you need to know two important numbers. There might be some locations from which every other location can be reached. There might also be locations that can be reached from every other location. You need to know how many of each of these there are.

The input will contain several test cases. The first line in the input contains the number of test cases N. For each test case: The first line contains one integer M (1 ≤ M ≤ 50), indicating the number of rooms. This is followed by M lines describing the way the locations have been connected. The ith line (beginning with the 0-th element) will contain a ‘1‘ (all quotes are for clarity only) in position j if there is a path that leads directly from i to j, and a ‘0‘ if there is not a path that leads directly from i to j.

For each test case, output two integers on a separate line, the first one is the number of locations that can reach all other locations, and the second one is the number of locations that are reachable by all other locations. There is a space between the two integers.

4
3
010
000
110
4
0010
1000
1100
1000
5
01000
00100
00010
00001
10000
7
0110000
1000100
0000001
0010000
0110000
1000010
0001000

1 1
1 3
5 5
1 3