201415: [AtCoder]ARC141 F - Well-defined Abbreviation

Memory Limit:1024 MB Time Limit:8 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给定 $N$ 个由 `A,B,C,D` 组成的串 $S_i(1\leqslant i\leqslant N)$。 对一个串 $T$ 定义如下操作: - 选择一个 $i\in[1,N]$,找到一个 $(l,r)$ 使得 $T[l\cdots r]=S_i$; - 把 $T[l\cdots r]$ 从 $T$ 中删除,并把首尾拼接起来。 不断重复以上操作知道任意 $S_i$ 都不是 $T$ 的子串。 我们称 $T$ 是好的,当且仅当操作后 $T$ 是唯一的。判断是否存在不好的串。 translated by cszyf

加入题单

上一题 下一题 算法标签: