题目描述
背景
SC theme Park 终于开业了,可爱的平平小朋友很荣幸的成为第一个游客。
公园设计强调,复杂就是美。scp大老板给他的公园设计了一个极其复杂的布局:
由于公园极大,而景点又很多,scp大老板在任意的两个景点之间都建造了一条星光小道,而且还为每条小道制定了方向。
题目描述
现在,平平从scp大老板那里得知公园总共有N个景点,并且已经知道了每一条星光小道的方向,但由于平平的方向感极差而RP又极低,于是一旦公园中出现回路,即存在环,平平便会迷路,并且无论怎么走都走不出去。
这样,scp大老板可就伤透脑筋了。为了使平平不会迷路,scp大老板决定改变其中M条星光小道的方向使得公园里不存在回路,但scp大老板又希望改变的小道的条数最少。由于很忙,腾不出时间,scp大老板只好请教即将参加noip的你。(注意:任意两个景点之间有且只有一条星光小道,且任意两条小道都是不相通的,即不能从一条小道不经过景点直接到达另一条小道)。
数据规模
对于30%数据,1<=N<=10;
对于100%数据,1<=N<=20.
输入格式
第一行有一个整数N,表示有N个景点。
接下来是一张N*N的矩阵,第i+1行第j列表示有无从景点i指向景点j的星光小道(0表示没有,1表示有)。
输出格式
输出仅包括一行,即M的最小值。
样例输入
样例输出