Connecting a Road Graph

There are N cities in a country. Some pairs of cities are connected by bidirectional roads. Eunjin wants to modify some roads so that every city becomes connected to every other city, while using as few modifications as possible.

One modification is performed as follows.

1. Choose four cities A, B, C, and D such that A and B are connected by a road, C and D are connected by a road, and none of A-C, A-D, B-C, or B-D is currently connected by a road.
2. Remove the roads A-B and C-D.
3. Add either the roads A-C and B-D, or the roads A-D and B-C.

Given N and the road information, find the minimum number of road modifications needed.

The first line contains N, a positive integer no greater than 50.

Each of the next N lines contains the road information as an adjacency matrix. If the character in row i and column j is Y, cities i and j are connected by a road; if it is N, they are not connected. The matrix is symmetric: g[i][j] = g[j][i], and every diagonal entry is N.

Output the minimum number of road modifications. If it is impossible, output -1.