问题陈述
N 存在一个由顶点组成的有向图。
当g_{i,j} = 1 时的顶点 i 到顶点
这意味着可以通过沿着边缘到达 j 存在一条有向边。
最初,所有顶点都被漆成白色。 Snuke 可以执行两次以下操作。
- 选择一个顶点并沿着该顶点的有向边访问多个顶点。您可以多次经过同一个顶点。
- 将所有经过一次或多次的顶点绘制为黑色。
经过两次操作,找到涂成黑色的顶点的最大数量。
约束
- 1 ≤ N ≤ 300
- 0 ≤ g_{i,j} ≤ 1
- g_{i,i} = 0
输入格式
输入将以以下格式从标准输入提供。
N
g_{1,1} ... g_{1,N}
...
g_{N,1} ... g_{N,N}
输出格式
如果您可以将棋子放置在第
示例输入 1
4
0 0 0 1
0 0 0 1
0 0 0 1
0 0 0 0
示例输出 1
例如,如果第一次追踪 1->4,第二次追踪 2->4,则 3 个顶点将被涂成黑色。
示例输入 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
示例输出 2
例如,如果第一次追踪 1->3->6->3->4,第二次追踪 2->3->5,则第 6 个顶点将被涂成黑色。