AT_abc167_f [ABC167F] Bracket Sequencing

题目描述

我们将满足以下任一条件的字符串定义为括号序列。

1. 空字符串。
2. 存在某个括号序列 $A$，将 (、$A$、) 按此顺序连接得到的字符串。
3. 存在某两个非空括号序列 $A$、$B$，将 $A$、$B$ 按此顺序连接得到的字符串。

给定 $N$ 个字符串 $S_i$。你可以以任意顺序连接所有 $S_i$，问是否可以构成一个括号序列。

输入格式

输入以以下格式从标准输入读入。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

如果可以以任意顺序连接 $S_i$ 使其构成括号序列，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

2
)
(()

输出 #1

Yes

输入输出样例 #2

输入 #2

2
)(
()

输出 #2

No

输入输出样例 #3

输入 #3

4
((()))
((((((
))))))
()()()

输出 #3

Yes

输入输出样例 #4

输入 #4

3
(((
)
)

输出 #4

No

说明/提示

限制

• $1 \leq N \leq 10^6$
• 所有 $S_i$ 的总长度不超过 $10^6$
• $S_i$ 仅由 ( 和 ) 组成，且为非空字符串

样例解释 1

按 (()、) 的顺序连接可以得到一个括号序列。

由 ChatGPT 4.1 翻译