Number of walks

A walk in a graph is a route that may pass through the same vertex and the same edge more than once. The length of a walk is the number of edges it contains.

Given a graph, write a program that finds the smallest nonnegative integer $K$ such that the number of walks of length $L$ is $O(L^K)$.

The number of walks being $O(L^K)$ means there is a constant $C$ such that the number of walks of length $L$ is at most $C \times L^K$ for every positive integer $L$.

The first line contains the number of vertices $N$ $(2 \le N \le 50)$.

Each of the next $N$ lines gives the edges of the graph as an adjacency matrix. If the $j$-th character of the $i$-th line is Y, there is an edge from vertex $i$ to vertex $j$; if it is N, there is no such edge. No edge joins a vertex to itself.

Print the smallest nonnegative integer $K$ that satisfies the condition. If no $K$ satisfies it, print -1.

If three vertices are joined to each other in both directions, the number of walks of length $L$ is $3 \times 2^L$. That value cannot be written as $O(L^K)$ for any $K$.

In a graph with no cycle, the number of walks of length $L$ is 0 once $L$ reaches $N$.

If the graph consists only of cycles that share no vertex, the number of walks of length $L$ equals $N$ for every $L$.