给定一个包含 $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”。在第二行输出构成欧拉回路且同时构成合法括号序列的顶点序列。如果存在多种解，输出其中任意一个即可。

样例

样例输入 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