F - Bracket Sequencing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

以下のいずれかの条件を満たす文字列を括弧列と定義します。

  1. 空文字列
  2. ある括弧列 A が存在して、(, A, ) をこの順に連結した文字列
  3. ある空でない括弧列 A, B が存在して、A, B をこの順に連結した文字列

N 個の文字列 S_i が与えられます。S_i 全てを好きな順序で連結するとき、括弧列を構成することはできますか。

制約

  • 1 \leq N \leq 10^6
  • S_i の文字列長の合計は 10^6 以下
  • S_i は (, ) のみからなる空でない文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
:
S_N

出力

S_i を任意の順序で連結するとき、括弧列を構成できるなら Yes、できないなら No を出力せよ。

入力例 1

2
)
(()

出力例 1

Yes

((), ) の順に連結すると括弧列になります。

入力例 2

2
)(
()

出力例 2

No

入力例 3

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

出力例 3

Yes

入力例 4

3
(((
)
)

出力例 4

No

Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

  1. An empty string;
  2. The concatenation of (, A, and ) in this order, for some bracket sequence A ;
  3. The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

  • 1 \leq N \leq 10^6
  • The total length of the strings S_i is at most 10^6.
  • S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No