Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3232
It's not Floyd Algorithm

Time Limit: 4 Seconds      Memory Limit: 32768 KB

When a directed graph is given, we can solve its transitive closure easily using the well-known Floyd algorithm.

But if you're given a transitive closure, can you give a corresponding directed graph with minimal edges?

Input

About 100 test cases, seperated by blank line.

First line of each case is an integer N (1<=N<=200). The following N lines represent the given transitive closure in 0-1 matrix form, each line has N numbers.

Output

For each case, just output the number of minimal edges of a directed graph which has a given transitive closure.

Sample Input
1
1

2
1 0
0 1

2
1 1
1 1

3
1 1 1
0 1 1
0 0 1
Sample Output
0
0
2
2
Hint

Transitive closure can be presented as a matrix T, where Ti,j is true if and only if there is a path from vertex i to j.


Author: CUI, Tianyi
Source: ZOJ Monthly, August 2009
Submit    Status