当前没有测试数据。

题目描述

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

格式

输入

第一行为一个整数 $n$。 接下来为 $n\times n$ 的矩阵 isConnected。

输出

一个整数，即 省份 的个数。

样例

3
1 1 0
1 1 0
0 0 1

2

3
1 0 0
0 1 0
0 0 1

3

提示

样例说明

样例一如下图：

样例二如下图：

数据范围

• $1 <= n <= 200$
• isConnected[i][j] 为 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]