J - Sub-Post Correspondence Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

うなぎ「上側と下側にそれぞれ文字列が書かれたカードが何種類かあって」

きつね「(Post Correspondence Problem だ……)」

うなぎ「それぞれのカードを何枚使ってもいいので，好きな順に並べて」

きつね「(Post Correspondence Problem だ……)」

うなぎ「上側と下側の文字列をそれぞれ繋げてできる 2 つの文字列を」

きつね「(Post Correspondence Problem だ……)」

うなぎ「なんとなく一致させてください」

きつね「(！？)」

問題文

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