31578번 - Play Onwards 스페셜 저지

문제

서훈이는 용훈이의 아재개그로 고통 받고 있다. 다음은 서훈이와 용훈이의 대화 중 일부이다.

용훈 : (휘파람을 불 듯이) 장미란에게 장미란 무엇일까~?

서훈 : (…)

서훈 : (간절하게) 용훈이형, 제발 그러지 좀 마.

매일 용훈이의 언어폭력(?)에 시달리고 있던 서훈이는 어느 날 용훈이와 함께 새로운 외국어를 배우기로 결심했다. 서훈이가 외국어 교재를 본 결과 그는 총 $N$개의 단어를 익혀야 한다는 것을 깨달았다.

외국어 교재에서 나오는 순서대로 $N$개의 단어를 외우면 좋겠지만, 서훈이는 외국어를 공부하는 동안 용훈이가 자신이 배운 단어들을 이용해서 아재개그를 하는 것을 경계하고 있다.

용훈이가 두 단어를 가지고 아재개그를 하려면 두 단어에서 길이가 $K$인 연속한 부분문자열을 잡아서 같게 만들 수 있어야 한다. 예를 들어 jangmiran과 jangmi는 길이 6인 문자열 jangmi를 포함하므로 $K$가 6 이하인 경우 용훈이는 두 단어를 가지고 아재개그를 할 수 있다. 반면 ant와 ainta는 nt를 포함하지만 ant를 포함하지 않으므로(ant는 ainta의 일부를 가지고 만들 수 있지만 연속하지 않다) $K=3$인 경우 용훈이는 두 단어를 가지고 아재개그를 할 수 없다.

서훈이는 단어장을 적절히 짜집기해서 두 개의 단어장을 만들려고 한다. 모든 단어는 두 개의 단어장 중 단 한 곳에서 나타나야 하고 각 단어장에는 단어가 최소 하나 있어야 한다.

서훈이는 용훈이가 두 단어장 중 어떤 단어장을 골라도 그 단어장의 단어를 가지고 아재개그를 할 수 없게 하려고 한다. 서훈이를 도와 용훈이가 아재개그를 할 수 없게 단어장을 짜주는 프로그램을 작성하여라.

입력

첫 번째 줄에 단어의 수 $N,ドル 용훈이가 아재개그를 하기 위해 필요한 최소 유사도 $K$가 주어진다. (3ドル \le N \le 200,ドル 1ドル \le K \le 20$)

두 번째 줄부터 $N$개의 줄에는 단어장에 있는 단어들의 알파벳 발음이 순서대로 주어진다. 단어는 알파벳 영어 소문자로만 이루어진 길이 1ドル$ 이상 20ドル$ 이하인 문자열이다.

서훈이와 용훈이가 동음이의어를 한 번에 모두 익히는 것이 아니므로 똑같은 단어가 단어장에 여러 번 나타날 수 있다.

출력

만약 서훈이가 단어장을 어떻게 만들어도 용훈이가 아재개그를 할 수 있다면 첫 번째 줄에 No만 출력한다. 그렇지 않다면 첫 번째 줄에 Yes를 출력하고 그 다음 $N$줄에 걸쳐 각 단어가 들어간 단어장 번호를 출력한다. 단어를 첫 번째 단어장에 넣어야 한다면 1을, 두 번째 단어장에 넣어야 한다면 2를 출력한다.

답이 여러 개인 경우 그중 아무거나 출력해도 정답으로 인정한다.

제한

힌트