You are given an undirected graph without self-loops or multiple edges which consists of n vertices and m edges. Also you are given three integers n_1, n_2 and n_3.

Can you label each vertex with one of three numbers 1, 2 or 3 in such way, that: 

  1. Each vertex should be labeled by exactly one number 1, 2 or 3; 
  2. The total number of vertices with label 1 should be equal to n_1; 
  3. The total number of vertices with label 2 should be equal to n_2; 
  4. The total number of vertices with label 3 should be equal to n_3; 
  5. |col_u - col_v| = 1 for each edge (u, v), where col_x is the label of vertex x. 



If there are multiple valid labelings, print any of them.

Input

The first line contains two integers n and m (1 ≤ n ≤ 5000; 0 ≤ m ≤ 10^5) — the number of vertices and edges in the graph.

The second line contains three integers n_1, n_2 and n_3 (0 ≤ n_1, n_2, n_3 ≤ n) — the number of labels 1, 2 and 3, respectively. It's guaranteed that n_1 + n_2 + n_3 = n.

Next m lines contan description of edges: the i-th line contains two integers u_i, v_i (1 ≤ u_i, v_i ≤ n; u_i ≠ v_i) — the vertices the i-th edge connects. It's guaranteed that the graph doesn't contain self-loops or multiple edges.

Output

If valid labeling exists then print "YES" (without quotes) in the first line. In the second line print string of length n consisting of 1, 2 and 3. The i-th letter should be equal to the label of the i-th vertex.

If there is no valid labeling, print "NO" (without quotes).

Examples

Input


6 3
2 2 2
3 1
5 4
2 5


Output


YES
112323


Input


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


Output


NO
import math

class Bags:
    def __init__(self):
        self.dictNodeColor = {}
        self.numOnes = 0
        self.numTwos = 0

def DFS(node,color,bags,visited):
    if(visited[node] and bags.dictNodeColor[node] != color):
        return True
    if(visited[node] ):
        return False
    bags.dictNodeColor[node] = color
    if(color == 1):
        bags.numOnes = bags.numOnes + 1
    else:
        bags.numTwos = bags.numTwos + 1
    visited[node] = True
    cycle = False
    if not node in dictGraph:
        return False
    for n in dictGraph[node]:
        if color == 1:
            cycle = DFS(n,2,bags,visited)
        else:
            cycle = DFS(n,1,bags,visited)
        if cycle:
            break
    return cycle
        

dictGraph = {}
#t = int(input())
t = 1#int(lines[counter])
for testcase in range(t):
    numVertices,numEdges=map(int,input().split())
    n1,n2,n3 = map(int,input().split())
    dictGraph = {}
    for i in range(numEdges):
        u,v = map(int,input().split())
        u = u-1
        v= v-1
        if u in dictGraph:
            dictGraph[u] = dictGraph[u] + [v]
        else:
            dictGraph[u] = [v]
        if v in dictGraph:
            dictGraph[v] = dictGraph[v] + [u]
        else:
            dictGraph[v] = [u]
    visited = [False]*numVertices
    allBags = []
    cycle = False;
    for i in range(numVertices):
        if(visited[i] == False):
            b = Bags()

            rs = DFS(i,1,b,visited)
            allBags.append(b)
            if(rs == True):
                cycle = True
                break
    if(cycle):
        print("NO")
    else:
        cols = n2
        rows = len(allBags)
        dp = [[-1 for cc in range(cols+1)] for rr in range(rows)]
        for col in range(cols + 1):
            if(allBags[0].numOnes == col):
                dp[0][col] = allBags[0].numOnes
            if(allBags[0].numTwos == col):
                dp[0][col] = allBags[0].numTwos
        for row in range(1,rows):
            i1 = allBags[row].numOnes
            i2 = allBags[row].numTwos
            for col in range(cols+1):
                if(col - i1 >= 0 and dp[row-1][col - i1] != -1):
                    dp[row][col] = i1
                elif(col - i2 >= 0 and dp[row-1][col - i2] != -1):
                    dp[row][col] = i2
        if(dp[rows-1][cols] == -1):
            print('NO')
        else:
            print('YES')
            dictAnswer = {}
            counter = len(allBags) - 1
            r = rows-1
            c = cols
            while(counter > -1):
                number = dp[r][c]
                bag = allBags[counter]
                twos = 2
                if(bag.numOnes == number):
                    twos = 1
                for key in bag.dictNodeColor:
                    if(bag.dictNodeColor[key] == twos):
                        dictAnswer[key] = 2
                    else:
                        if(n1 > 0):
                            dictAnswer[key] = 1
                            n1 = n1 -1
                        else:
                            dictAnswer[key] = 3
                counter = counter - 1
                r = r-1
                c= c-number
            answer = ''
            for i in range(numVertices):
                answer += str(dictAnswer[i])
            print(answer)