← 返回题目列表

Codeforces · 1055/D

D. 重构

中文机器翻译题面 查看原题

Alice 编写了一个程序,现在尝试提高其可读性。提高可读性的方法之一是为变量指定合理的名称,因此现在 Alice 想重命名程序中的一些变量。在她的IDE中有一个名为“大规模重构”的命令,只需一次运行即可替换许多变量的名称。要使用它,Alice 需要选择两个字符串 $$$s$$$ 和 $$$t$$$,然后对每个变量执行以下算法:如果变量的名称包含 $$$s$$$ 作为子字符串,则第一个(也是唯一第一个)出现的 $$$s$$$ 被替换为 $$$t$$$。如果名称不包含 $$$s$$$,则该变量的名称保持不变。

变量列表是已知的,并且对于每个变量,初始名称和 Alice 希望此变量更改的名称都是已知的。此外,对于每个变量,初始名称和目标名称的长度是相等的(否则代码的对齐可能会被破坏)。您需要在一次大规模重构命令运行中对所有变量进行重命名,或者确定这是不可能的。

输入

第一行包含唯一的整数 $$$n$$$ ($$$1 \le n \le 3000$$$) — Alice 程序中的变量数量。

以下 $$$n$$$ 行包含变量 $$$w_1、w_2、\ldots、w_n$$$ 的初始名称,每行一个。之后,继续执行 $$$n$$$ 行,其中第 $$$i$$$ 行包含第 $$$i$$$ 变量的目标名称 $$$w'_i$$$ 。保证 $$$1 \le |w_i| = |w'_i| \le 3000$$$。

保证至少有一个变量的目标名称与初始名称不同。初始名称和目标名称均仅由小写英文字母组成。对于每个变量,其初始名称的长度等于其目标名称的长度。

输出

如果不可能通过一次“大规模重构”重命名所有变量,请打印“NO”(为了清晰起见,用引号引起来)。

否则,在第一行打印“YES”(为了清晰起见,用引号括起来),并在接下来的行打印 $$$s$$$ 和 $$$t$$$ ($$$1 \le |s|, |t| \le 5000$$$),这应该用于替换。字符串 $$$s$$$ 和 $$$t$$$ 只能包含英文字母的小写字母。

如果有多种方法来执行“大规模重构”,您可以使用其中任何一种。

示例

输入 #1

1
topforces
codecoder

输出 #1

YES
topforces
codecoder

输入 #2

3
bab
cac
cdc
bdb
cdc
cdc

输出 #2

YES
a
d

输入 #3

2
you
shal
not
pass

输出 #3

NO