← 返回题目列表

AtCoder · past202206_d

D. 相似的字符串

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

分数: 7 点

问题陈述

我们有成对的小写英文字母 (a_1,b_1),(a_2,b_2),\dots,(a_N,b_N).

两个小写英文字母 u 和 v 据说是 类似 如果存在 i 这样 (u,v)=(a_i,b_i) or (u,v)=(b_i,a_i).

两个字符串 U 和 V 具有相同的长度据说是 类似 if U 和 V 满足以下条件:

  • 你可以使 U 等于 V 通过重复(可能零次)选择以下字符之一 U 并将其替换为类似的字符。

给定字符串 S 和 T 长度相同,判断是否 S 和 T 类似。

约束

  • 1 \leq N \leq 325
  • N 是一个整数。
  • a_i 和 b_i 是不同的小写英文字母。
  • If i \neq j,那么 (a_i,b_i) \neq (a_j,b_j) 和 (a_i,b_i) \neq (b_j,a_j).
  • S 和 T 是长度介于 1 和 100,包括在内。
  • S 和 T 具有相同的长度。

输入

输入由标准输入按以下格式给出:

N
a_1 b_1
a_2 b_2
\vdots
a_N b_N
S
T

输出

If S 和 T 类似,打印 Yes;否则,打印 No.


示例输入 1

1
m n
man
nan

示例输出 1

Yes

我们可以使 通过执行操作1一次和操作3一次获得 S 等于 T 通过替换 1-st 字符 S 与 n, 制作 S nan。 自从 m 和 n 是相似的字符, S 和 T 满足相似字符串的条件。


示例输入 2

1
m n
man
men

示例输出 2

No

示例输入 3

3
a b
a e
d e
abc
edc

示例输出 3

Yes

示例输入 4

1
a b
xyz
xyz

示例输出 4

Yes