시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB61627423144.253%

문제

다솜제국의 왕 이다솜은 화가 났다. 그래서 자신의 나라의 모든 길을 바꾸려고 한다.

현재 다솜제국에는 여러 개의 마을이 있다. 각각의 마을은 일방통행인 도로나 양방통행인 도로로 연결되어 있다. 이다솜의 목표는 양방통행인 도로를 모두 일방통행으로 바꾸는 것이다. 이 말은 양방통행인 도로를 두 개의 방향 중 하나로 선택하는 것이다.

이다솜의 궁극적인 목표는 양방통행인 도로를 모두 일방통행으로 바꿔서 임의의 도시 x에서 출발해서 다시 그 도시 x로 돌아올 수 없게 만드는 것이다.

도로의 정보가 주어졌을 때, 이다솜의 목표를 실천할 수 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N(2 ≤ N ≤ 50) 이 주어진다.  둘째 줄부터 N개의 줄에 도로의 정보가 주어진다. 인접행렬처럼 주어진다. i행 j열이 의미하는 정보는 Y 또는 N인데, Y일 때는 i에서 j으로 가는 도로가 있다는 소리고, N일 때는 없다는 소리다. i번 행의 i번 열에 있는 문자는 항상 N이다.

출력

이다솜의 목표를 실천할 수 있으면 YES, 없으면 NO를 출력한다.

예제 입력 1

3
NYN
YNY
NYN

예제 출력 1

YES

예제 입력 2

3
NYN
YNY
NYN

예제 출력 2

YES

예제 입력 3

4
NYNN
NNYN
YNNY
NNYN

예제 출력 3

NO

예제 입력 4

3
NNN
NNN
NNN

예제 출력 4

YES

예제 입력 5

5
NYYYY
YNYYY
YYNYY
YYYNY
YYYYN

예제 출력 5

YES

출처