题目内容

在一个声学实验室中，有 $n$ 个待测样本，每个样本都有一个固有频率。若两个样本的固有频率相等，则称它们“同频”。已知同频关系满足自反性、对称性和传递性，因此所有样本被划分成若干个同频等价类，同一等价类内的样本频率均相同，不同等价类的频率互不相同。

实验人员发现，至少存在一个样本的固有频率恰好为 $0$（称为零频样本）。根据等价类性质：若某个样本为零频样本，则它所在的整个等价类内所有样本均为零频样本；同时，由于不同等价类的频率不同，至多只能有一个等价类的频率为 $0$。

请你计算在所有可能情形下，零频样本数量的最小可能值与最大可能值。

约束条件：

• 样本数量 $n$ 满足 $1 \le n \le 500$。
• 输入矩阵中的所有元素均为 $0$ 或 $1$，且保证表示的关系是自反、对称且传递的。

输入描述

第一行包含一个整数 $n$，表示样本总数。 接下来 $n$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 列的整数 $a_{i,j}$ 表示样本 $i$ 与样本 $j$ 是否同频（$1$ 表示同频，$0$ 表示不同频）。

输出描述

输出两个整数，以空格分隔，分别表示零频样本数量的最小可能值和最大可能值。

样例1

输入

3
1 1 0
1 1 0
0 0 1

输出

1 2

说明

样本 1 与样本 2 同频，样本 3 自成一类。等价类的大小分别为 2 和 1。

由于零频样本必然恰好出现在某一个等价类中，且该等价类中的所有样本均为零频，因此零频样本的数量可以是 2（若频率为 $0$ 的是大等价类）或 1（若频率为 $0$ 的是小等价类）。在所有可能情形下，最小可能值为 1，最大可能值为 2。

样例2

输入

1
1

输出

1 1

说明

只有一个样本，它自身构成一个等价类，大小为 1。因为题目保证至少存在一个零频样本，所以该样本必须为零频样本。

零频样本数量只能是 1，因此最小可能值与最大可能值均为 1。

样例3

输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出

4 4

说明

所有样本两两同频，形成一个完整的等价类，大小为 4。

根据题目条件，至少存在一个零频样本，从而整个等价类中的全部 4 个样本都必须是零频样本。此时零频样本的数量只能为 4，因此最小值与最大值均为 4。