The existence of a walk satisfying the conditions is actually equivalent to the existence of a walk with the following properties:

• The start and end vertices are the same, and each edge is used at least once.
• The number of edges labeled ( equals the number of edges labeled ) (counting multiple occurrences if used multiple times).

This is because a string containing an equal number of ( and ) can be transformed into a valid parentheses string by circular shifting it so that the substring with the minimum difference between the number of opening and closing parentheses will be the suffix (for example, if the string is )())((, circular shifting it four times to (()()) results in a regular bracket sequence). Therefore, if we find a walk satisfying the above properties, we can reselect an appropriate starting vertex to obtain a walk satisfying the original conditions. From here on, we consider determining the existence of a walk satisfying the above properties.

A walk can be thought of as a combination of several cycles (it can be seen that a combination of cycles forms a walk by considering the existence condition of an Eulerian circuit). Therefore, one way to construct a walk satisfying the conditions is:

• For each edge, choose a cycle that uses that edge, and combine them to form a walk. The existence of such a cycle is guaranteed by the strong connectivity of the graph.
• To balance the numbers of ( and ), traverse the initially constructed walk multiple times or add new cycles for adjustment.

For example, if we initially have a cycle \(C_1\) with eight more (s than )s, and a cycle \(C_2\) with three fewer (s than )s, we can obtain a walk satisfying the conditions by taking a walk that traverses \(C_1\) three times and a walk that traverses \(C_2\) eight times and reconstructing an Eulerian circuit.

Although it may seem that a walk satisfying the conditions can be obtained in most cases by multiplying cycles as described above, it is important to note that we cannot traverse a cycle a negative number of times. Therefore, it is crucial whether a cycle has more (s or more )s.

In the following, we consider cases based on the existence of cycles with more (s or more )s.

1. Both types of cycles exist

In this case, we can select and adjust cycles based on which parenthesis is more abundant in the initially constructed walk, as described in the construction above.

2. Neither type of cycle exists

This means that every cycle has an equal number of ( and ). Therefore, it can be concluded that the initially constructed walk also has an equal number of ( and ), and thus a walk satisfying the conditions exists.

3. Only one type of cycle exists

In this case, a walk satisfying the conditions does not exist. We will prove this by contradiction. Without loss of generality, assume that a cycle with more (s exists.

Suppose there is a walk \(C_1\) satisfying the conditions. We also take a cycle \(C_2\) with more (s. Since \(C_1\) uses all edges at least once, we can remove the edges used in \(C_2\) from \(C_1\). The remaining part can be divided into several Eulerian circuits. These contain more )s than (s. In particular, at least one of the Eulerian circuits has more )s than (s, contradicting the initial assumption.

The above observations reduce the problem to determining the existence of two types of cycles. The former can be done by determining the existence of a negative cycle in a graph where edges labeled ) have a weight of \(1\) and edges labeled ( have a weight of \(-1\), which can be performed in \(O(NM)\) time using the Bellman-Ford algorithm, which is sufficiently fast. For the latter, one can reverse the weights.