10627번 - Parentheses 다국어

You are given \(n\) strings \(\mathit{str}_1, \mathit{str}_2, \ldots, \mathit{str}_n\), each consisting of ( and ). The objective is to determine whether it is possible to permute the \(n\) strings so that the concatenation of the strings represents a valid string.

Validity of strings are defined as follows:

• The empty string is valid.

• If \(A\) and \(B\) are valid, then the concatenation of \(A\) and \(B\) is valid.

• If \(A\) is valid, then the string obtained by putting \(A\) in a pair of matching parentheses is valid.

• Any other string is not valid.

For example, "()()" and "(())" are valid, while "())" and "((()" are not valid.

The first line of the input contains an integer \(n\) (\(1 \leq n \leq 100\)), representing the number of strings. Then \(n\) lines follow, each of which contains \(\mathit{str}_i\) (\(1 \leq \lvert \mathit{str}_i \rvert \leq 100\)). All characters in \(\mathit{str}_i\) are ( or ).

Output a line with "Yes" (without quotes) if you can make a valid string, or "No" otherwise.