I came across this question while going through Goldman Sach's previous year questions asked in online assessment. I am stuck with this for quite some time now and any help regarding the same will be appreciated.

*Anaximander was a Greek traveller and philosopher who travelled all over the world going from city to city. After returning home from his travels, he created a map of his travels, using his knowledge of cities and roads that connected all those cities. While he remembered all the cities and connecting roads, he could not recall how many countries he actually visited during his travels. However, he did recall that all countries had two characteristics - first, each country had at least three cities in it, and second, all the cities within a country were connected to each other by a direct road.

*Given the map details, help Anaximander to determine the number of countries he visited.
*
The map details are given as an adjacency matrix where cities are represented by rows and columns. The value of 0 or 1 is given in each cell of the matrix, where 1 represents that a direct road exists between cities represented by that row and column, and 0 means that there is no direct road.

First line contains an Integer n, the number of cities. Next n lines contain n values of 0 or 1 each, representing the cities and connecting roads. The first row has detalls of the roads connecting to city 1, second row has city 2 and so on.

Output format:

Output contains the total number of countries present in the world map.

Sample input 1:

6
011000
101000
110100
001011
000101
000110

Sample Output 1:
2

Explanation: In the given map, cities at position 0, 1 and 2 are connected to each other and cities at position 3, 4 and 5 are connected to each other. Hence these form two countries each.

Sample input 2:
9
011000000
101000000
110100000
001011000
000101000
000110100
000001011
000000110

Sample Output 2:
3

What I could think of is that the question requires us to find cliques of size greater than or equal to 3. Since the value of n can be at most 103, I think some sort of a brute force solution may also suffice. However, I am not able to arrive at the same.