Making Roads One-Way

The kingdom has N cities. A road between two cities may be one-way, allowing travel in only one direction, or two-way, allowing travel in both directions.

The king wants to replace every two-way road with a one-way road. For each two-way road, exactly one of its two possible directions may be chosen.

After all changes, there must be no city x such that one can start at x, follow roads, and return to x. Given the road information, determine whether such a replacement is possible.

The first line contains the number of cities N (2 <= N <= 50).

Each of the next N lines contains an N-character string describing the roads. The j-th character of the i-th line is either Y or N. Y means there is a road from city i to city j, and N means there is no such road. The i-th character of the i-th line is always N.

Print YES if the replacement is possible; otherwise print NO.