Another Contest 2 Problem 2 - Poutine

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 256M

Problem type

Fast Fingers Thomas has just finished conducting a tryout for a poutine-eating contest, and needs to produce a ranklist. However, the scoreboard has crashed and the rankings are lost! Individual i beat individual j if individual i ate more poutine than individual j. He vaguely remembers that some individuals ate more poutine than other individuals, but might not have enough data to fully reconstruct the ranklist. He does remember that there were no ties in the contest.

He decides to email all the participants with a list of pairs of individuals, and expects to get a response with, for each pair, which individual did better.

Compute the minimum possible size of the list such that, independent of what responses he gets back with regards to which individual ate more poutine, he is guaranteed to be able to construct a correct full ranklist.


1 \le N \le 500

There exists some ranklist consistent with the input.

Input Specification

The first line contains a single positive integer, N.

The next N lines contain a binary string of length N. If the jth character of the ith line is 1, then individual i definitely did better than individual j. Otherwise, the jth character of the ith line is 0.

Output Specification

Output the minimum number of pairs needed to always ascertain the ranklist.

Sample Input


Sample Output



There are no comments at the moment.