解题思路

题目中给出的“相对静止”满足：

• $a_{i,i}=1$
• $a_{i,j}=a_{j,i}$
• 具有传递性

因此，这个关系本质上是一个等价关系。

题目内容

一天，一群列车约好一起赛跑，在赛跑过程中，列车之间可能产生相对静止现象，即速度相等时看起来好像静止。现在给定$n$辆列车的相对静止矩阵信息，其中至少存在一辆列车真正静止。请你计算可能真正静止的列车数量的最小值和最大值

输入描述

第一行输入整数$n (1 ≤ n ≤ 500)$ 表示列车数量。

此后$n$行，每行输入$n$个整数$a_{i,j}$ ($1 ≤ i, j ≤ n$; $a_{i,j}$ ∈ {$0, 1$})，其中$a_{i,j }= 1$表示第$i$辆列车与第$j$辆列车相对静止，否则不相对静止；并且保证$a_{i,i} = 1$且$a_{i,j }= a_{j,i}$。保证相对静止关系具有传递性，即若$i, j$相对静止且$j, k$相对静止，则$i, k$必然相对静止

输出描述

输出两个整数，分别表示可能的最小值和最大值。两数之间用空格分隔。

样例1

输入

2
1 0
0 1

输出

1 1