#2757 끝말잇기

16  1 s   128 MB  

Description

끝말잇기는 이 전 단어의 마지막 글자로 시작하는 새로운 단어를 말하며 이어가는 게임이다. 각 사람은 자신 바로 이전의 사람이 말한 단어의 끝 글자로 시작하는 단어를 말해야 한다. 물론 존재하지 않는 터무니없는 단어는 사용할 수 없으므로 이 게임은 전적으로 어휘력이 풍부한 사람이 유리하다.

연애에 서툰 복학생인 우태는 신입생과 친해지기 위하여 MT 에 가기에 앞서 끝말잇기 게임을 준비했다.

단, 몇몇 신입생에게 점수를 따고 싶은 우태는 자신이 원하는 대로 게임이 흘러갈 수 있도록 몇 가지 아래와 같은 규칙을 정했다.

 

• 이 게임에서 사용되는 모든 단어는 영어이다.

• 사전의 모든 단어는 항상 사전순으로 정렬되어있다.

• 게임에 참가하는 모든 사람은 우태가 만든 끝말잇기 사전에 적힌 단어들 만을 사용할 수 있다.

• 우태가 만든 사전에 없는 영단어는 사용할 수 없으며, 사전에 있는 단어는 실존하지 않는 단어여도 상관없다.

• 한 사람이 단어를 말하면, 다음 사람이 말하는 단어의 첫 글자는 이 전 사람이 말한 단어의 마지막 글자와 같아야 한다.

 

MT 에 가기 전에 자신이 원하는 대로 끝말잇기 사전을 만들고, 미리 모든 단어를 외워둔 우태는 기대에 가득 차 있었다. 하지만 MT 에 가지 않기로 결정한 모태솔로 재현이는 연서복 우태가 자신처럼 신입생과 친분이 없기를 바랬다. 그래서 재현이는 우태가 동방에 둔 사전을 몰래 훔쳐서 사전에 적힌 단어를 조작해버렸다!

재현이는 우태의 사전을 훔쳐서 각 단어를 구성하는 알파벳을 사전순으로 정렬해버렸다! 즉, 예를 들어 우태의 사전에 lovelyz 라는 단어가 있었다면 재현이가 조작한 사전에는 ellovyz 로 바뀌어 있게 된다.

 

원본 사전

조작된 사전

apple

banana

eat

kiwi

trick

aaabnn

aelpp

aet

cikrt

iikw

<재현이가 사전을 조작하는 예시>

 

위의 예시에서 원본 사전의 단어로는 banana-apple-eat-trick-kiwi 순서로 모든 단어를 한번씩만 사용하여 게임을 끝낼 수 있다. 이런 경우를 우태는 성공적 게임이라고 한다.

MT 에 도착해서 사전이 조작되었다는 사실을 알게 된 우태는 이미 게임의 규칙을 후배들에게 설명해버려서 조작된 사전을 가지고 게임을 진행하는 수 밖에 없었다. 그래도 희망을 버리지 않은 우태는 당신에게 조작된 사전을 가지고도 성공적 게임이 가능한 지 확인해 달라는 부탁을 했다. 불쌍한 연서복 우태를 도와주자. 

Input

첫 줄에 사전에 적힌 단어의 개수를 나타내는 자연수 N 이 주어진다. N 2 10 사이의 정수이다.

그 후 N 줄에 걸쳐서 각 줄에 하나씩 조작 된 사전에 존재하는 단어들이 사전 순으로 정렬된 순서로 주어진다. 각 단어의 길이는 1 글자에서 10 글자 사이다.

모든 입력은 소문자로 주어진다.

Output

조작된 사전에 존재하는 단어들을 모두 한 번씩만 사용하여 정확히 N 번만에 게임이 끝나는 경우가 가능하다면 “YES”를 출력한다. 그렇지 않다면 “NO”를 출력한다.

Sample Input

Sample Output

5
aaabnn
alpp
aet
cikrt
iikw
NO

Source

shake 2016! 본선