D. Directed 67
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As a waterpark director, you have to plan the rides. You already know that your rides will look like a directed graph with $$$n$$$ vertices and $$$m$$$ edges. However, you don't know yet how long each of the edges will be, which is determined by the edge's weight. Based on the materials you have, each weight should be one of the digits $$$d_1, d_2, \ldots, d_k$$$.

The weight of a directed path is the sum of the digits assigned to the edges of the path (edges in a path are allowed to repeat).

You know that if there is a directed path of weight $$$w$$$ divisible by $$$67$$$, it will become the only ride used, and you want to avoid that. Provide the assignment, where there is no path with weight divisible by 67, or determine there is no such assignment.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 200000$$$).

The second line contains a non-empty string $$$s$$$ consisting of distinct characters from 1 to 9. These are the allowed digits $$$d_i$$$ ($$$1 \le d_i \le 9$$$).

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$). This means that there is a directed edge from $$$u_i$$$ to $$$v_i$$$. Multiple edges and self-loops are allowed.

Output

If there is no valid assignment, print NO.

Otherwise, print YES on the first line.

On the second line print $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$, where $$$a_i$$$ is the digit assigned to the $$$i$$$-th edge. Each $$$a_i$$$ must be one of the allowed digits.

If there are several valid assignments, print any of them.

Examples
Input
2 1
3
1 2
Output
YES
3
Input
4 3
679
1 2
1 3
3 4
Output
YES
6
7
7
Input
3 3
123
1 2
2 3
3 1
Output
NO