AT_abc302_c [ABC302C] Almost Equal

题目描述

给定 $N$ 个由小写英文字母组成、长度为 $M$ 的字符串 $S_1, S_2, \dots, S_N$。其中，任意两个 $S_i$ 互不相同。

请判断是否存在一种排列 $T_1, T_2, \dots, T_N$，满足以下条件：

• 对于所有满足 $1 \leq i \leq N-1$ 的整数 $i$，可以仅通过将 $T_i$ 中的一个小写字母替换为另一个小写字母，使其变为 $T_{i+1}$。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

如果存在满足题目条件的排列，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

4 4
bbed
abcd
abed
fbed

输出 #1

Yes

输入输出样例 #2

输入 #2

2 5
abcde
abced

输出 #2

No

输入输出样例 #3

输入 #3

8 4
fast
face
cast
race
fact
rice
nice
case

输出 #3

Yes

说明/提示

限制条件

• $2 \leq N \leq 8$
• $1 \leq M \leq 5$
• $S_i$ 是由小写英文字母组成的长度为 $M$ 的字符串（$1 \leq i \leq N$）
• 任意两个 $S_i$ 互不相同。

样例解释 1

将字符串按 abcd、abed、bbed、fbed 的顺序排列，可以满足题目条件。

样例解释 2

无论如何排列，都无法满足题目条件。

由 ChatGPT 4.1 翻译