#P3755. 四川算法设计大赛-第5题-排列字符串
-
ID: 2748
传统题
2500ms
512MiB
尝试: 15
已通过: 2
难度: 9
上传者:
18829573624
标签> 四川算法设计大赛-第5题-排列字符串
当前没有测试数据。
Description
你有 n 个长度为 m 的仅包含小写字母的字符串 \(S_1, S_2, \dots, S_n\)。
请问是否存在一个 1 ~ n 的排列 \(p_1, p_2, \dots, p_n\) 使得对于任意 \(1 \leq i < n\) 均满足 \(S_{p_i}\) 在删除第一个字符再在末尾添加一个字符后可以等于 \(S_{p_{i + 1}}\)。
Input Format
【输入格式】 每个测试点包含多组测试数据。 第一行一个正整数 T 表示数据组数。 对于每组测试数据，第一行两个正整数 n，m。 接下来第 i 行，每行一个长度为 m 且只包含小写字母的字符串 \(S_i\)。Output Format
【输出格式】 输出 T 行， 对于第 i 行，输出 YES 表示可以找到这样的排列，否则输出 NO。2
5 3
vfe
ete
tev
evf
fet
5 3
zbc
cpf
ezb
pfb
bcpYES
YESHint
【样例1解释】
对于第1组数据，
evf vfe fet ete tev是一个合法的序列；
对于第2组数据，
ezb zbc bcp cpf pfb是一个合法的序列。
| 测试点编号 | n | m |
|------------|-------|-----|
| 1 ~ 2 | = 8 | = 5 |
| 3 ~ 4 | = 20 | = 10|
| 5 ~ 6 | = 5000| = 10|
| 7 | = 10^5| = 10|