QOJ.ac

QOJ

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

#9834. 键盘混乱

Statistics

你有没有想过,普通的平面键盘很无聊,而你可以想出一些更有趣的东西?

一个小男孩 Kevin 发明了一种带有 $n$ 个不寻常按键的键盘。每个按键 $i$ 最初包含一个字母序列:$L_{i,1}, L_{i,2}, \dots, L_{i,|L_i|}$。序列中的某些字母可能相同。每个字母都是前 $e$ 个小写英文字母之一。

每当按下按键 $i$ 时,其序列中的第一个字母会被输入,并立即移动到序列的末尾。因此,第一次按下按键 $i$ 时,字母 $L_{i,1}$ 被输入,序列变为 $L_{i,2}, \dots, L_{i,|L_i|}, L_{i,1}$。第二次按下按键 $i$ 时,字母 $L_{i,2}$ 被输入,序列变为 $L_{i,3}, \dots, L_{i,|L_i|}, L_{i,1}, L_{i,2}$,依此类推。

例如,假设按键 1 包含序列 'a', 'b', 'a',按键 2 包含序列 'c', 'd'。那么,如果按此顺序按下按键 2, 1, 2, 2, 1, 1, 1, 2,将输入字符串 "cadcbaad"。

请帮助 Kevin 了解他的键盘有多么“有用”,并找出由前 $e$ 个小写英文字母组成的、无法通过给定的初始状态使用该键盘输入的长度最短的字符串。

输入格式

第一行包含两个整数 $n$ 和 $e$,分别表示按键的数量和字母表的大小 ($1 \le n \le 100; 2 \le e \le 26$)。

接下来的 $n$ 行,第 $i$ 行包含字符 $L_{i,1}, L_{i,2}, \dots, L_{i,|L_i|}$,表示按键 $i$ 最初包含的字母序列 ($1 \le |L_i| \le 10$)。每个字符都是前 $e$ 个小写英文字母之一。

输出格式

输出由前 $e$ 个小写英文字母组成的、无法通过 Kevin 的键盘从初始状态输入的长度最短的字符串。如果存在多个长度最短的字符串,输出其中任意一个即可。

如果任何字符串都可以被输入,则输出字符串 "NO"。

样例

样例输入 1

1 26
win

样例输出 1

f

样例输入 2

3 3
abc
bca
cab

样例输出 2

aa

样例输入 3

4 2
aab
bb
a
bab

样例输出 3

NO

说明

在第一个测试用例中,唯一能用 Kevin 的键盘输入的字符串是 "winwinwinwin..." 的前缀。由于你不能以除 'w' 以外的任何字母开头,因此除 'w' 之外的任何小写英文字母都是正确答案。

在第二个测试用例中,"bb" 和 "cc" 是其他可能的答案。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.