← 返回题目列表

AtCoder · xmascon19_j

J. 子帖对应问题

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

配点 : 100 点

鳗鱼“上方和下方各自写有字符串的卡片有几种”

狐狸:“(邮政对应问题……)”

鳗鱼:“每张卡可以使用任意次数,按自己喜欢的顺序排列”

狐狸:“(邮政对应问题……)”

鳗鱼:“将上方和下方的字符串分别连接起来” 2 鳗鱼:“得到的字符串”

狐狸:“(邮政对应问题……)”

鳗鱼:“请尽量让它们匹配”

狐狸:“(!?)”

問題文

N 每种卡各有 2019^{2019} 张。

i 第种卡的上方写有字符串 A_i 下方写有字符串 B_i 被写了。

从这些卡中 1 张或更多,选择并按喜欢的顺序排列成一列。此时,将排列好的每张卡上方写的字符串拼接起来为 s,下方写的字符串拼接起来为 t 。

能否选择并排列卡片以满足以下条件?

  • 条件: s 减去 0 通过选择并删除任意位置的字符(字符数限制为以上) t 可以使其与 相匹配。

制約

  • 1 \leq N \leq 16.
  • 1 \leq |A_i|, |B_i| \leq 10^5.
  • A_i, B_i 仅由小写英文字母组成的字符串。

入力

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

如果有可能选择并排列卡片以满足条件, YES,否则 NO 。


入力例 1

2
cab ac
acba ab

出力例 1

YES

例如, 不要以指数表示法输出,如2 種類目,2 種類目,1 按照种类的顺序排列卡片,s = acbaacbacab, t = ababac 将变为 ,这满足条件。


入力例 2

1
xmas contest

出力例 2

NO