J - Sub-Post Correspondence Problem /

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