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 beat individual if individual ate more poutine than individual . 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.
There exists some ranklist consistent with the input.
The first line contains a single positive integer, .
The next lines contains a binary string of length . If the th character of the th line is
1, then individual
definitely did better than individual . Otherwise, the th character of the th line is
Output the minimum number of pairs needed to always ascertain the ranklist.
3 011 000 000