Bracket Euler Tour

You are given an undirected graph with $n$ vertices and $m$ edges. Each vertex has a bracket (either opening “(” or closing “)”) associated with it.

You have to find an Euler tour in this graph such that its vertices (written in traversal order) form a correct bracket sequence.

A correct bracket sequence is a sequence of brackets that can be transformed into a correct arithmetic expression by inserting characters “1” and “+” between the original characters of the sequence. For example, bracket sequences “()()” and “(())” are correct (the resulting expressions are “(1)+(1)” and “((1+1)+1)”). In contrast, “)(” and “()(” are not.

An Euler tour of an undirected graph is a cycle which visits every edge in the graph exactly once. Visiting the same vertex multiple times is allowed.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$), the number of vertices and edges respectively.

Each of the following $m$ lines contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$), meaning that there is an undirected edge between vertices $v_i$ and $u_i$. Self-loops and multiple edges are allowed.

The last line of the input contains a string of $n$ round brackets, where the $i$-th bracket is associated with vertex $i$.

If there is no Euler tour in the given graph that forms a correct bracket sequence, print “No” in the first line.

Otherwise, print “Yes” in the first line. In the second line, print a sequence of vertices that forms an Euler tour and also a correct bracket sequence. If there are multiple solutions, print any of them.