시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 29 7 7 24.138%

문제

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 “()()”, “(())” are correct (the resulting expressions are “(1)+(1)” and “((1+1)+1)”), while “)(” and “()(” are not.

An Euler tour of an undirected graph is a cycle which visits every edge in this graph exactly once. It is allowed to visit the same vertex multiple times, though.

입력

The first line contains two integers n and m (1 ≤ n, m ≤ 2 · 105), the number of vertices and edges respectively.

Each of the following m lines contains two integers vi and ui (1 ≤ vi, ui ≤ n), meaning that there is an undirected edge between vertices vi and ui. Note that 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 form an Euler tour and also a correct bracket sequence. If there are multiple solutions, print any of them.

예제 입력 1

2 2
1 2
1 2
)(

예제 출력 1

Yes
2 1

예제 입력 2

5 6
1 2
2 3
3 1
2 4
4 5
5 2
(()))

예제 출력 2

Yes
1 2 4 5 2 3

예제 입력 3

1 1
1 1
(

예제 출력 3

No