← 返回题目列表

AtCoder · abc167_f

F. 括号排序

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

A 括号序列 是以下字符串之一:

  1. 空字符串;
  2. 的串联 (, A,和 ) 按此顺序,对于某些括号序列 A ;
  3. 的串联 A 和 B 按此顺序,对于某些非空括号序列 A 和 B /

给出的是 N 字符串 S_i。能否将所有的括号串联起来 N 字符串按某种顺序排列?

约束

  • 1 \leq N \leq 10^6
  • 字符串的总长度 S_i 最多是 10^6.
  • S_i 是一个非空字符串,包含 ( 和 ).

输入

输入由标准输入按以下格式给出:

N
S_1
:
S_N

输出

如果一个括号序列可以通过连接所有 N 按某种顺序排列的字符串,打印 Yes;否则,打印 No.


示例输入 1

2
)
(()

示例输出 1

Yes

连接 (() 和 ) 以此顺序形成括号序列。


示例输入 2

2
)(
()

示例输出 2

No

示例输入 3

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

示例输出 3

Yes

示例输入 4

3
(((
)
)

示例输出 4

No