The king of Absurdistan has become very angry, and thus he has decided to make an evil reform of the road network.
Currently, the network contains several towns, connected by some one-way and some two-way streets. The king's goal is to change all two-way streets into one-way streets. That is, for each currently present two-way street the king will pick one of the two directions,
and make the street one-way in the chosen direction.
To make it even worse, the king has a simple goal he wants to achieve: After the reform the network must be so evil that once someone starts traveling along the roads, he will never be able to return back to the town where he started.
You will be given the current map as a String roads.
More precisely, the towns are numbered from 0 to N-1 for some N.
The j-th character of the i-th element of roads is 'Y' if there is a direct road that allows us to travel from i to j, otherwise it will be 'N'.
Each pair of towns is connected by at most one direct road. If the input contains a 'Y' both for a i->j road and for a j->i road, this means that the road between i and j is currently two-way.
Write a method that will return
either "YES" or "NO" (quotes for clarity), depending on whether the king can achieve his evil goal.