괄호 오일러 투어

정점 $n$개와 간선 $m$개로 이루어진 무방향 그래프가 주어진다. 각 정점에는 여는 괄호 “(” 또는 닫는 괄호 “)”가 하나씩 대응된다.

이 그래프에서 오일러 투어를 하나 찾아야 한다. 이때 투어를 따라가며 방문한 정점들을 순서대로 나열한 것이 올바른 괄호열이어야 한다.

올바른 괄호열은 원래 문자들 사이에 “1”과 “+”를 넣어 올바른 산술식으로 바꿀 수 있는 괄호열이다. 예를 들어 “()()”, “(())”는 올바른 괄호열이다(각각 “(1)+(1)”, “((1+1)+1)”이 된다). 반면 “)(”와 “()(”는 올바르지 않다.

무방향 그래프의 오일러 투어는 그래프의 모든 간선을 정확히 한 번씩 지나는 사이클이다. 같은 정점을 여러 번 방문해도 된다.

첫째 줄에 정점의 수 $n$과 간선의 수 $m$이 주어진다. ($1 \le n, m \le 2 \cdot 10^5$)

다음 $m$개 줄에는 정수 $v_i$와 $u_i$가 주어진다. ($1 \le v_i, u_i \le n$) 이는 정점 $v_i$와 $u_i$를 잇는 무방향 간선이 있음을 뜻한다. 자기 루프와 중복 간선이 허용된다.

마지막 줄에는 길이 $n$의 둥근 괄호 문자열이 주어지며, $i$번째 괄호가 정점 $i$에 대응된다.

주어진 그래프에 올바른 괄호열을 이루는 오일러 투어가 없으면 첫째 줄에 “No”를 출력한다.

그렇지 않으면 첫째 줄에 “Yes”를 출력한다. 둘째 줄에는 오일러 투어를 이루면서 올바른 괄호열이기도 한 정점 수열을 출력한다. 해가 여러 개면 아무거나 출력한다.