P16308 [ICPC 2023 Jinan R] Many Many Heads.

Many Heads Cup, abbreviated as MHC, is a world-class programming contest for contestants who have $\textbf{many many heads}$. The chief judge of this contest, Little Mackerel, is considering designing an ID number for each contestant. “Then, let’s use this,” Little Mackerel thought, “let’s use some bracket sequences!” He assigns each contestant a unique balanced bracket sequence. Each sequence contains two types of brackets: parentheses (also called round brackets), and square brackets. To make sure you understand what a balanced bracket sequence is, Little Mackerel prepared the following formal definition: - $\varepsilon$ (an empty string) is a balanced bracket sequence. - If $A$ is a balanced bracket sequence, then $(A)$ and $[A]$ are also balanced bracket sequences. - If $A$ and $B$ are balanced bracket sequences, then $AB$ is also a balanced bracket sequence. For example, $\tt{()}$, $\tt{[()]}$, and $\tt{[()]()}$ are balanced bracket sequences, but $\tt{)(}$, $\tt{[(])}$, and $\tt{[)}$ are not. For our contestants with many heads, memorizing bracket sequences is not difficult. However, the problem lies in their unique ability: because they have too many heads, they cannot tell the direction of a bracket. As a result, compared to the original balanced bracket sequence, the sequence in their memory may have some brackets flipped. For example, the bracket sequence $\tt{[()]()}$ might be remembered as $\tt{]))]))}$ or $\tt{]()]))}$. Fortunately, the bracket type still remains unchanged. :::align{center}  ::: On the contest day, after Little Mackerel received each contestant’s bracket sequence, a question arose: can the original bracket sequence be uniquely determined? In other words, Little Mackerel needs to determine whether the given bracket sequence corresponds to exactly one balanced bracket sequence. Please help Little Mackerel complete this task, so that our many-headed friends can participate in the contest.

There are multiple test cases. The first line contains an integer $T$ denoting the number of test cases. For each test case: The first line contains a string $S$ consisting of $\tt{(}$, $\tt{)}$, $\tt{[}$, and $\tt{]}$ ($1 \leq |S| \leq 10^5$), representing the bracket sequence. It is guaranteed that: - The sum of $|S|$ over all test cases does not exceed $10^6$. - Each bracket sequence is obtained by flipping the direction of some brackets in a certain balanced bracket sequence.

For each test case: - If the given bracket sequence can correspond to more than one balanced bracket sequence, output one line $\tt{No}$. - Otherwise, output one line $\tt{Yes}$.

For the first sample, the bracket sequence corresponds to exactly one balanced bracket sequence: $\tt{()}$. So the answer is $\tt{Yes}$. For the second sample, the bracket sequence can correspond to two different balanced bracket sequences: $\tt{(())}$ and $\tt{()()}$. So the answer is $\tt{No}$. For the third sample, the bracket sequence corresponds to exactly one balanced bracket sequence: $\tt{[()]}$. So the answer is $\tt{Yes}$. For the fourth sample, the bracket sequence can correspond to two different balanced bracket sequences: $\tt{(([()]))}$ and $\tt{()[()]()}$. So the answer is $\tt{No}$. For the fifth sample, the bracket sequence corresponds to exactly one balanced bracket sequence: $\tt{([()])}$. So the answer is $\tt{Yes}$. For the sixth sample, the bracket sequence can correspond to three different balanced bracket sequences: $\tt{([])([])}$, $\tt{([]()[])}$, and $\tt{([[()]])}$. So the answer is $\tt{No}$. Translated by ChatGPT 5