Kattis

# Bracket Matrix

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