e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ADA Classes - November 6

Connected components

The undirected unweighted graph is given. Find the number of its connected components.

Input

The first line contains the number of vertices n (n100) in a graph. In each of the next n rows n numbers are given - the adjacency matrix of the graph: in the i-th row of the j-th place there is a 1 if the vertices i and j are connected by an edge, and 0 otherwise. The main diagonal of the matrix contains zeroes. The matrix is symmetric with respect to the main diagonal.

Output

Print the number of connected components in a graph.

prb2269.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
Output example #1
3
Source 2011 Summer school, Sevastopol, August 8, Day 1, League 1