Hide

Problem B
Bracket Matrix

/problems/bracketmatrix/file/statement/en/img-0001.jpg
Image by GamerDruid

A bracket sequence consisting of ‘(’ and ‘)’ is defined to be valid as follows:

  1. An empty sequence is valid.

  2. If $x$ is a valid bracket sequence, then $(x)$ is a valid bracket sequence.

  3. If $x$ and $y$ are valid bracket sequences, then the concatenation of $x$ and $y$, $z=xy$, is a valid bracket sequence.

You are given a bracket matrix of size $n \times n$, in which each cell has a single bracket. Each row of the matrix, read from left to right, presents a bracket sequence. You may modify the matrix by choosing two brackets in a same column and swapping their positions. You may make any number of swaps (possibly zero). Can you make every row of the matrix present a valid bracket sequence?

Input

The first line has an even integer $n$ ($2 \leq n \leq 2\, 000$). Each of the next $n$ lines has $n$ brackets giving one row of the bracket matrix.

Output

If you can obtain a valid bracket sequence on every row of the matrix, output “Yes”. Otherwise, output “No”.

Sample Input 1 Sample Output 1
4
((()
()))
()))
((()
Yes
Sample Input 2 Sample Output 2
2
()
)(
No

Please log in to submit a solution to this problem

Log in