曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6090: park

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：21 Solved：1
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

SC theme Park 终于开业了，可爱的平平小朋友很荣幸的成为第一个游客。
公园设计强调，复杂就是美。scp大老板给他的公园设计了一个极其复杂的布局：
由于公园极大，而景点又很多，scp大老板在任意的两个景点之间都建造了一条星光小道，而且还为每条小道制定了方向。
现在，平平从scp大老板那里得知公园总共有N个景点，并且已经知道了每一条星光小道的方向，但由于平平的方向感极差而RP又极低，于是一旦公园中出现回路，即存在环，平平便会迷路，并且无论怎么走都走不出去。
这样，scp大老板可就伤透脑筋了。为了使平平不会迷路，scp大老板决定改变其中M条星光小道的方向使得公园里不存在回路，但scp大老板又希望改变的小道的条数最少。由于很忙，腾不出时间，scp大老板只好请教即将参加noip的你。（注意：任意两个景点之间有且只有一条星光小道，且任意两条小道都是不相通的，即不能从一条小道不经过景点直接到达另一条小道）。

Input

第一行有一个整数N，表示有N个景点。
接下来是一张N*N的矩阵，第i+1行第j列表示有无从景点i指向景点j的星光小道（0表示没有，1表示有）。

Output

输出仅包括一行，即M的最小值。

Sample Input Copy 

4
0 0 0 0
1 0 1 0
1 0 0 1
1 1 0 0

Sample Output Copy 

1

HINT

对于30%数据,1<=N<=10;
对于100%数据,1<=N<=20.