问题陈述。

给定一个简单（无自循环和多条边）且相连的无向图，图中有 $N$ 个顶点和 $M$ 条边。 对于 $i = 1, 2, \ldots, M$ ，第 $i$ 条边是连接顶点 $u_i$ 和顶点 $v_i$ 的无向边。

请判断是否有一种将每个顶点涂成白色或黑色的方法同时满足以下 $2$ 两个条件，如果有，请举例说明。

• $1$ 多个顶点被涂成黑色。
• 对于所有 $i = 1, 2, \ldots, K$ ，以下条件都成立。
  • 顶点 $p_i$ 与 "与顶点 $p_i$ 距离最小的涂黑顶点 "之间的距离正好是 $d_i$ 。

这里，顶点 $u$ 和顶点 $v$ 之间的距离定义为连接 $u$ 和 $v$ 的路径中可能的最小边数。

限制。

• $1 \leq N \leq 2000$
• $N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace$
• $1 \leq u_i, v_i \leq N$
• $0 \leq K \leq N$
• $1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N$
• $0 \leq d_i \leq N$
• 给定图形简单且连通
• 所有输入均为整数

输入。

输入通过标准输入，格式如下。

$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

$K$

$p_1$ $d_1$

$p_2$ $d_2$

$\vdots$

$p_K$ $d_K$

输出。

如果无法将每个顶点涂成白色或黑色以满足问题陈述中的条件，则输出 "否"。 如果存在，则在第 $1$ 行输出 "是"，并在第 $2$ 行输出代表每个顶点涂色方法的字符串 $S$ ，格式如下。 其中，{7595951638}是长度为 $N$ 的字符串， $i = 1, 2, \ldots, N$ 的 $S$ 的 $i$ 字符为 $1$ ，将顶点 $i$ 绘制为黑色时为 $1$ ，将顶点 $i$ 绘制为白色时为 $0$ 。

Yes
S

如果答案不止一个，则以输出的答案为准。

入力例 1

5 5
1 2
2 3
3 1
3 4
4 5
2
1 0
5 2

输出示例 1

Yes
10100

例如，将顶点 $1, 3$ 涂成黑色，将顶点 $2, 4, 5$ 涂成白色，就满足了问题陈述中的条件。 事实上，对于 $i = 1, 2, 3, 4, 5$ ，顶点 $i$ 与 "与顶点 $i$ 距离最小的涂成黑色的顶点 "之间的距离是 $A_i$ 和 $(A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2)$ ，尤其是 $A_1 = 0, A_5 = 2$ 成立。

入力例 2

5 5
1 2
2 3
3 1
3 4
4 5
5
1 1
2 1
3 1
4 1
5 1

输出示例 2

No

输出 "否"，因为无法将每个顶点涂成白色或黑色以满足问题陈述中的条件。