103022: [Atcoder]ABC302 C - Almost Equal

Problem Statement

You are given $N$ strings $S_1,S_2,\dots,S_N$, each of length $M$, consisting of lowercase English letter. Here, $S_i$ are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings $T_1,T_2,\dots,T_N$ such that:

• for all integers $i$ such that $1 \le i \le N-1$, one can alter exactly one character of $T_i$ to another lowercase English letter to make it equal to $T_{i+1}$.

Constraints

• $2 \le N \le 8$
• $1 \le M \le 5$
• $S_i$ is a string of length $M$ consisting of lowercase English letters. $(1 \le i \le N)$
• $S_i$ are pairwise distinct.

Input

The input is given from Standard Input in the following format:

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

Output

Print Yes if one can obtain a conforming sequence; print No otherwise.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

问题描述

你将得到$N$个长度为$M$的字符串$S_1,S_2,\dots,S_N$，每个字符串由小写英文字母组成。这里，$S_i$两两不同。

确定是否可以重新排列这些字符串，得到一个新的字符串序列$T_1,T_2,\dots,T_N$，满足以下条件：

• 对于所有满足$1 \le i \le N-1$的整数$i$，可以将$T_i$中的一个字符改为另一个小写英文字母，使其等于$T_{i+1}$。

约束

• $2 \le N \le 8$
• $1 \le M \le 5$
• $S_i$是一个长度为$M$的字符串，由小写英文字母组成。 $(1 \le i \le N)$
• $S_i$两两不同。

输入

输入从标准输入以以下格式给出：

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

输出

如果可以得到一个符合条件的序列，打印Yes；否则打印No。

样例输入1

4 4
bbed
abcd
abed
fbed

样例输出1

Yes

可以按照这个顺序重新排列它们：abcd，abed，bbed，fbed。这个序列满足条件。

样例输入2

2 5
abcde
abced

样例输出2

No

无论字符串如何重新排列，条件永远不会得到满足。

样例输入3

8 4
fast
face
cast
race
fact
rice
nice
case

样例输出3

Yes