\problemname{Watch Where You Step}

You are an employee at the local zoo and have recently been promoted from
excretory extraction to overseeing the layout of all the sidewalks throughout
the property.  Currently all the sidewalks are $1$-way, and the zoo is set up in
various {\em zones}.  Each zone is made up of a set of {\em attractions\/}
(elephant enclosure, lizard house, etc.), and within any one zone you can get
from any attraction to any other attraction in the zone using one or more
sidewalks.  Once you take a sidewalk from one zone to another you can never
return to the zone you left. However, it is possible to walk to every zone
in a single visit to the zoo. The original designers thought this arrangement
was very important to help control the flow of visitors to the zoo.

The members of the board of directors have come to you with a problem.  They
agree with the original designers in the use of zones, but they feel that more
one-way sidewalks could be included to make the zoo a little more
patron-friendly.  They would like you to figure out the maximum number of
sidewalks that could be added so as not to introduce a path between any two
attractions which didn't have one between them before.

For example, consider the small zoo shown in Figure \ref{fig:zoo}, with $7$
attractions labeled $1$ (the ``Camel Castle'') through $7$ (the ``Hippo
Hippodrome'').  Currently attractions $1$, $2$, $3$ and $4$ form one
zone and $5$, $6$ and $7$ form another.  You can add sidewalks from $1$, $2$,
$3$ or $4$ to
either $5$, $6$ or $7$, but adding a sidewalk from (say) $7$ to $1$ would allow patrons
to get from $7$ to $1$, which was impossible previously.  Note that you can also
add sidewalks between all attractions within a zone which don't already exist
(for example, from $1$ to $3$ or from $2$ to $4$).  The total number of possible new
sidewalks for this zoo would be $21$. 

%\begin{figure}[!h] \centering \setlength{\unitlength}{3pt}
%\begin{picture}(30,10)(0,0) \put( 0, 0){\circle{4}} \put( 0,
%0){\makebox(0,0){D}} \put(10, 0){\circle{4}} \put(10, 0){\makebox(0,0){C}}
%\put(20, 0){\circle{4}} \put(20, 0){\makebox(0,0){G}} \put( 0,10){\circle{4}}
%\put( 0,10){\makebox(0,0){A}} \put(10,10){\circle{4}}
%\put(10,10){\makebox(0,0){B}} \put(20,10){\circle{4}}
%\put(20,10){\makebox(0,0){E}} \put(30,10){\circle{4}}
%\put(30,10){\makebox(0,0){F}} \put( 2,10){\vector(1,0){6}}
%\put(12,10){\vector(1,0){6}} \put(22,10){\vector(1,0){6}} \put( 8,
%0){\vector(-1,0){6}} \put( 0, 2){\vector(0,11){6}} \put(20, 2){\vector(0,1){6}}
%\put(10, 8){\vector(0,-1){6}} \put(1.4, 1.4){\vector(1,1){7.2}} \put(28.6,
%8.6){\vector(-1,-1){7.2}} \end{picture} \caption{Sample zoo.} \label{fig:zoo}
%\end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=.5\textwidth]{finalzoo.png}
\caption{Sample zoo. This example corresponds to Sample Input $1$.}
\label{fig:zoo}
\end{figure}

\section*{Input} Input starts with a line containing an integer $n$ ($1 \leq n
\leq 2\,500$), the number of attractions, labeled $1$ to $n$.  After this are $n$
lines each containing $n$ integers.  If the $j^{th}$ integer on the $i^{th}$ of
these lines is a $1$ it indicates that there is a one-way sidewalk from
attraction $i$ to attraction $j$; otherwise this integer will be a $0$ indicating
no such sidewalk is present. There is never a sidewalk from an attraction
to itself.

\section*{Output} Display the maximum number of new one-way sidewalks that
could be added to the zoo.

%\section*{Comment} Need to find strongly connected components (does the sample
%figure make this too obvious?) and then determine how many edges you can add
%between components that aren't there already.
%
%Just thought of a better name for the problem: Watch Where You Step.  If we use
%it, we'll have to change the folder name.
