配点 : 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