#P12115. [NWRRC2024] Keyboard Chaos

[NWRRC2024] Keyboard Chaos

Description

你是否曾觉得普通的平面键盘太过无聊,想要设计些更有趣的东西?

一个叫 Kevin 的小男孩设计了一个有 nn 个特殊按键的键盘。每个按键 ii 初始包含一个字母序列:Li,1,Li,2,,Li,LiL_{i,1}, L_{i,2}, \ldots, L_{i,|L_i|}。序列中可能有重复字母。每个字母都是前 ee 个小写英文字母之一。

每次按下按键 ii 时,会输入其序列的第一个字母,并立即将该字母移到序列末尾。因此,第一次按下按键 ii 时输入字母 Li,1L_{i,1},序列变为 Li,2,,Li,Li,Li,1L_{i,2}, \ldots, L_{i,|L_i|}, L_{i,1};第二次按下时输入 Li,2L_{i,2},序列变为 Li,3,,Li,Li,Li,1,Li,2L_{i,3}, \ldots, L_{i,|L_i|}, L_{i,1}, L_{i,2},以此类推。

例如,假设按键 11 的序列是 a\tt{a}, b\tt{b}, a\tt{a},按键 22 的序列是 c\tt{c}, d\tt{d}。若按顺序按下 2,1,2,2,1,1,1,22,1,2,2,1,1,1,2,将输入字符串 cadcbaad\tt{cadcbaad}

请帮助 Kevin 评估他的键盘功能,找出从初始状态开始,该键盘无法输入的最短字符串(仅由前 ee 个小写字母组成)。

Input Format

第一行包含两个整数 nnee,分别表示按键数量和字母表大小(1n1001 \le n \le 1002e262 \le e \le 26)。

接下来的 nn 行中,第 ii 行包含字符 Li,1,Li,2,,Li,LiL_{i,1}, L_{i,2}, \ldots, L_{i,|L_i|},表示按键 ii 的初始字母序列(1Li101 \le |L_i| \le 10)。每个字符都是前 ee 个小写英文字母之一。

Output Format

输出该键盘从初始状态开始无法输入的最短字符串(由前 ee 个小写字母组成)。若有多个最短字符串,输出任意一个即可。

若可以输入所有可能的字符串,则输出单个字符串 NO\tt{NO}

1 26
win
f
3 3
abc
bca
cab
aa
4 2
aab
bb
a
bab
NO

Hint

在第一个测试用例中,键盘只能输入 winwinwinwin...\tt{winwinwinwin...} 的前缀。由于无法以 w\tt{w} 以外的字母开头,任何非 w\tt{w} 的小写字母都是正确答案。

在第二个测试用例中,bb\tt{bb}cc\tt{cc} 也是可能的正确答案。