Keyboard Chaos

시간 제한2초메모리 제한2048 MB

요약
주어진 각 키의 문자 순환열에서 시작해 만들 수 없는, 처음 e개 알파벳으로 된 가장 짧은 문자열을 구한다.
난이도

어려움10점 중 9점

유형
BFS, 그래프, 문자열, 게임 이론
정답자
아직 제출이 없습니다

문제

Haven't you ever thought that an ordinary flat keyboard is boring, and you can come up with something more interesting?

A little boy named Kevin came up with a keyboard with nn unusual keys. Each key ii initially contains a sequence of letters: L_i,1,L_i,2,…,L_i,∣L_i∣L\_{i, 1}, L\_{i, 2}, \ldots, L\_{i, |L\_{i}|}. Some letters in this sequence can be equal. Each letter is one of the first ee lowercase English letters.

Every time key ii is pressed, the first letter of its sequence is typed and immediately moved to the end of the sequence. Thus, the first time key ii is pressed, letter L_i,1L\_{i, 1} is typed, and the sequence becomes L_i,2,…,L_i,∣L_i∣,L_i,1L\_{i, 2}, \ldots, L\_{i, |L\_{i}|}, L\_{i, 1}. The second time key ii is pressed, letter L_i,2L\_{i, 2} is typed, and the sequence becomes L_i,3,…,L_i,∣L_i∣,L_i,1,L_i,2L\_{i, 3}, \ldots, L\_{i, |L\_{i}|}, L\_{i, 1}, L\_{i, 2}, and so on.

For example, suppose that key 11 contains the sequence 'a', 'b', 'a', and key 22 contains the sequence 'c', 'd'. Then, if you press keys 2,1,2,2,1,1,1,22, 1, 2, 2, 1, 1, 1, 2 in this order, the string "cadcbaad" will be typed.

Help Kevin understand how useful his keyboard is, and find the shortest possible string consisting of the first ee lowercase English letters that cannot be typed with such a keyboard from the given initial state.

입력

The first line contains two integers nn and ee, denoting the number of keys and the size of the alphabet (1≤n≤1001 \le n \le 100; 2≤e≤262 \le e \le 26).

The ii-th of the following nn lines consists of characters L_i,1,L_i,2,…,L_i,∣L_i∣L\_{i,1}, L\_{i,2}, \ldots, L\_{i, |L\_i|}, denoting the sequence of letters key ii initially contains (1≤∣L_i∣≤101 \le |L\_{i}| \le 10). Every character is one of the first ee lowercase English letters.

출력

Print the shortest possible string, consisting of the first ee lowercase English letters, that can not be typed using Kevin's keyboard from the initial state. If there are multiple shortest strings, print any of them.

If any string can be typed, print a single string "NO" instead.

힌트

In the first test, the only strings that can be typed with Kevin's keyboard are prefixes of "winwinwinwin...". Since you can not start the string with any letter other than 'w', any lowercase English letter except 'w' is a correct answer.

In the second test, "bb" and "cc" are other possible answers.

예제3

  1. 예제 1

    입력
    1 26
    win
    
    예상 출력
    f
    
  2. 예제 2

    입력
    3 3
    abc
    bca
    cab
    
    예상 출력
    aa
    
  3. 예제 3

    입력
    4 2
    aab
    bb
    a
    bab
    
    예상 출력
    NO