/ 
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
A, B, C, D のみからなる N 個の文字列 S_i\ (1\le i \le N) が与えられます。
A, B, C, D のみからなる文字列 T に対し、以下の操作を考えます。
- どの S_i も T の部分文字列にならなくなるまで、以下を繰り返す。
- S_i, および T が S_i を含む場所をひとつ選び、その場所から S_i を取り除いて前後を連結する
部分文字列とは？
部分文字列とは連続する部分列のことを指します。例えばA, AB, BC は ABC の部分文字列ですが、BA や AC は ABC の部分文字列ではありません。
T が「悪い文字列」であるとは、T に対する操作結果として得られる文字列が複数存在することをいいます。
「悪い文字列」が存在するか判定してください。
制約
- 1 \leq N \leq 10^6
- 1 \leq |S_i| \leq 2 \times 10^6
- |S_1|+|S_2|+\dots +|S_N| \leq 2 \times 10^6
- i\neq j ならば S_i \neq S_j
- S_i は
A,B,C,Dのみからなる文字列
入力
入力は以下の形式で標準入力から与えられます。
N S_1 S_2 \vdots S_N
出力
「悪い文字列」が存在する場合、 Yes と出力してください。
存在しない場合、 No と出力してください。
入力例 1
3 A B C
出力例 1
No
T に対する操作結果として得られる文字列は T から A, B, C をすべて除いたもののみです。
入力例 2
1 ABA
出力例 2
Yes
例えば T=ABABA に対する操作の結果として得られる文字列は AB, BA の 2 つあるので T は「悪い文字列」です。
入力例 3
4 CBA ACB AD CAB
出力例 3
Yes
Score : 1100 points
Problem Statement
You are given N srings S_i\ (1\le i \le N) consisting of A, B, C, D.
Consider the operation below on a string T consisting of A, B, C, D.
- Repeat the following until T contains none of the strings S_i as a substring.
- Choose an S_i and one of its occurrences in T, remove that occurrence from T, and concatenate the remaining parts.
What is a substring?
A substring of a string is its contiguous subsequence. For example,A, AB, and BC are substrings of ABC, while BA and AC are not.
We say that the string T is bad when multiple strings can result from the operation above.
Determine whether a bad string exists.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq |S_i| \leq 2 \times 10^6
- |S_1|+|S_2|+\dots +|S_N| \leq 2 \times 10^6
- S_i \neq S_j if i\neq j.
- S_i is a string consisting of
A,B,C,D.
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
If a bad string exists, print Yes.
Otherwise, print No.
Sample Input 1
3 A B C
Sample Output 1
No
The only string we can get from T is what remains after removing all occurrences of A, B, C from T.
Sample Input 2
1 ABA
Sample Output 2
Yes
For example, from T= ABABA, we can get two strings: AB and BA, so T is a bad string.
Sample Input 3
4 CBA ACB AD CAB
Sample Output 3
Yes