题面描述

给定一个 $N * N$ 的矩阵，表示 $N$ 台服务器之间的连接关系：

• 如果 $matrix[i][j] == 1$，则表示服务器 $i$ 和服务器 $j$ 直接连接；
• 如果 $matrix[i][j] \neq 1$，则表示服务器 $i$ 和服务器 $j$ 不直接连接；
• 每台服务器与自身直接连接，即 $matrix[i][i] == 1$；
• 矩阵是对称的，即 $matrix[i][j] == matrix[j][i]$。

目标：计算最少需要广播的服务器数量，使得每台服务器都能接收到广播信息。

题目内容

服务器连接方式包括直接相连，间接相连。$A$ 和 $B$ 直接连接，$B$ 和 $C$ 直接连接，则 $A$ 和 $C$ 间接连接。直接连接和间接连接都可以发送广播。

给出一个 $N * N$ 数组，代表 $N$ 个服务器，

• $matrix[i] [j] == 1$ ，则代表 $i$ 和 $j$ 直接连接；不等于 $1$ 时 ，代表 $i$ 和 $j$ 不直接连接。
• $matrix[i] [i] == 1$ , 即自己和自己直接连接。
• $matrix[i] [j] == matrix[j] [i]$ 。

计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。

输入描述

输入为 $N$ 行，每行有 $N$ 个数字，为 $0$ 或 $1$ ，由空格分隔，构成 $N*N$ 的数组， $N$ 的范围为 $1 <= N <= 40$

输出描述

输出一个数字，为需要广播的服务器的数量

样例1

输入

1 0 0
0 1 0
0 0 1

输出

3

说明

$3$ 台服务器互不连接，所以需要分别广播这 $3$ 台服务器

样例2

输入

1 1
1 1

输出

1

说明

$2$ 台服务器互相连接，所以只需要广播其中一台服务器