Terminal Cities

Time limit2sMemory limit128 MB

Summary

Given a connected graph with up to 15 cities, find a spanning tree that maximizes the number of vertices with degree exactly one.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Tree, Graph
Solved: No attempts yet

Problem

There are N cities. Some pairs of cities are connected by bidirectional roads, and in the initial road network every city can reach every other city.

To reduce maintenance cost, some roads may be closed. As many roads as possible should be removed, but the remaining roads must still allow every city to reach every other city.

In the remaining road network, a city is called a terminal city if it is directly connected to exactly one other city. Using only roads from the given network while preserving connectivity, find the maximum possible number of terminal cities.

Input

The first line contains the number of cities N. N is at most 15.

The next N lines contain the adjacency matrix. If the j-th character of a row is 1, there is a road between that row's city and city j; if it is 0, there is no such road.

Output

Print the maximum possible number of terminal cities.

Examples5

Example 1
Input
```
5
01000
10100
01010
00101
00010
```
Expected output
```
2
```
Example 2
Input
```
2
01
10
```
Expected output
```
2
```
Example 3
Input
```
5
01111
10000
10000
10000
10000
```
Expected output
```
4
```
Example 4
Input
```
4
0111
1011
1101
1110
```
Expected output
```
3
```

Example 5

Input

Expected output