R - グラフ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 頂点からなる有向グラフがある。g_{i,j} = 1 であるとき頂点 i から頂点 j への有向辺がある。 最初に、すべての頂点は白く塗られている。すぬけ君は、以下の操作を二回行うことができる。
  • ある頂点を選び、その頂点から有向辺をたどっていくつかの頂点に訪れる。同じ頂点を複数回とおってもよい。
  • 一回以上通った頂点をすべて黒く塗る。
二回の操作後、黒く塗られた頂点の個数の最大値を求めよ。

Constraints

  • 1 ≤ N ≤ 300
  • 0 ≤ g_{i,j} ≤ 1
  • g_{i,i} = 0

Input Format

入力は以下の形式で標準入力から与えられる。
N
g_{1,1} ... g_{1,N}
...
g_{N,1} ... g_{N,N}

Output Format

答えを一行に出力せよ。

Sample Input 1

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

Sample Output 1

3
たとえば、1 回目に 1->4, 2 回目に 2->4 とたどると 3 頂点が黒く塗られる。

Sample Input 2

6
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0

Sample Output 2

6
たとえば、1 回目に 1->3->6->3->4, 2 回目に 2->3->5 とたどると 6 頂点が黒く塗られる。