이메일 파괴
면접 대비시간 제한3초메모리 제한512 MB
n, k와 'Re: ' 접두사가 반복된 서로 다른 이메일 제목 k개가 주어질 때, 삭제 전에 총 n개의 메일이 있었던 경우가 가능한지 판정합니다.
문제
ICPCorrespondence.com에 계정이 하나 있다. 이메일 서비스에서는 제목에 따라 이메일이 체인으로 묶인다.
각 체인의 첫 번째 이메일 제목은 비어 있지 않고 영어 소문자로만 이루어진다. 체인의 이후 이메일 제목은 전부 "Re: " 뒤에 이전 이메일의 제목이 붙은 형태다.
예를 들어 체인의 첫 이메일 제목이 "subj"이면 두 번째 이메일 제목은 "Re: subj", 세 번째는 "Re: Re: subj"가 된다. 일반적으로 체인의 k번째 이메일 제목은 "Re: "가 k − 1번 반복된 뒤 체인의 첫 이메일 제목이 붙은 형태다.
받은편지함에는 서로 다른 제목을 가진 하나 이상의 이메일 체인이 있었다. 어떤 이메일도 삭제한 적이 없다.
그런데 어느 날 ICPCorrespondence.com이 해커의 공격을 받았다. 그 결과 일부 이메일은 서버에서 삭제되었고, 남은 이메일의 순서는 뒤섞였다.
공격 전 받은편지함에 몇 통의 이메일이 있었는지는 확실하지 않지만, 그 수가 n이라고 추측한다. 이 추측이 맞을 수 있는지 확인할 수 있는가?
입력
입력의 첫 줄에 두 정수 n과 k가 주어진다. 각각 공격 전 받은편지함에 있었다고 생각하는 이메일 수와 공격 후 남은 이메일 수다 (1 ≤ k ≤ n ≤ 100).
다음 k개 줄에는 받은편지함에 남은 이메일의 제목이 한 줄에 하나씩 주어진다. 각 이메일의 제목은 "Re: "가 0번 이상 반복된 뒤, 1개 이상 10개 이하의 영어 소문자가 붙은 형태다. 각 제목의 길이는 500을 넘지 않는다. 모든 이메일 제목은 서로 다르다.
출력
공격 전 받은편지함의 이메일 수에 대한 추측이 맞을 수 있으면 "YES"를, 아니면 "NO"를 한 단어로 출력한다.
힌트
첫 번째 예시에서는 추측이 맞을 수 있다. 예를 들어 제목이 "hello", "Re: hello", "Re: Re: hello", "Re: Re: Re: hello", "Re: Re: Re: Re: hello", "world", "Re: world"인 이메일이 있었을 수 있다.
두 번째 예시에서는 "pleasehelp" 체인에 이메일이 적어도 세 통, "me" 체인에 적어도 한 통 있어야 하므로 추측이 틀렸다.