Making Roads One-Way

Interview

Time limit2sMemory limit128 MB

Summary

Decide if every two-way road between N cities can be made one-way so that no directed cycle remains in the whole road network.

Level: Medium6 of 10
Topics: Graph, DFS, Topological sort
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples5

Example 1
Input
```
3
NYN
YNY
NYN
```
Expected output
```
YES
```
Example 2
Input
```
3
NYN
YNY
NYN
```
Expected output
```
YES
```
Example 3
Input
```
4
NYNN
NNYN
YNNY
NNYN
```
Expected output
```
NO
```
Example 4
Input
```
3
NNN
NNN
NNN
```
Expected output
```
YES
```
Example 5
Input
```
5
NYYYY
YNYYY
YYNYY
YYYNY
YYYYN
```
Expected output
```
YES
```