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 java.util.*;

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;;

public class E {
	static BufferedReader br;
	static PrintWriter pw;
	static int inf = (int) 1e9;
	static long mod = (long) 1e9 + 7;

	static ArrayList<Integer> primes; // generated by sieve

	/*
	 * 1. Generating a list of prime factors of N
	 */
	static ArrayList<Long> primeFactors(Long N) // O(sqrt(N) / ln sqrt(N))
	{
		ArrayList<Long> factors = new ArrayList<Long>(); // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);

		while (p * p <= N) {
			if (N % p == 0)
				factors.add((long) p);
			while (N % p == 0) {
				N /= p;
			}
			if (idx + 1 == primes.size())
				break;
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			factors.add(N); // for integers whose largest prime factor has a power of 1
		return factors;
	}

	static int[] isComposite;

	static void sieve(int N) // O(N log log N)
	{
		isComposite = new int[N + 1];
		isComposite[0] = isComposite[1] = 1; // 0 indicates a prime number
		primes = new ArrayList<Integer>();

		for (int i = 2; i <= N; ++i) // can loop till i*i <= N if primes array is not needed O(N log log sqrt(N))
			if (isComposite[i] == 0) // can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				if (1l * i * i <= N)
					for (int j = i * i; j <= N; j += i) // j = i * 2 will not affect performance too much, may alter in
														// modified sieve
						isComposite[j] = 1;
			}
	}

	public static void main(String[] args) throws NumberFormatException, IOException, InterruptedException {
//		br = new BufferedReader(new FileReader(new File("chief.in")));
		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		n1 = Integer.parseInt(st.nextToken());
		n2 = Integer.parseInt(st.nextToken());
		n3 = Integer.parseInt(st.nextToken());

		adjList = new ArrayList[n];
		for (int i = 0; i < adjList.length; i++) {
			adjList[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			adjList[u].add(v);
			adjList[v].add(u);
		}
		vis = new boolean[n];
		color = new int[n];
		Arrays.fill(color, -1);
		arr = new ArrayList<>();
		boolean f = true;
		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				f &= isBipartite(i);
				if (f)
					arr.add(new pair(sum.x, sum.y));
			}
		}
		if (f) {
			memo = new int[arr.size()][n];
			for (int i = 0; i < memo.length; i++) {
				Arrays.fill(memo[i], -1);
			}
			int dp = dp(0, 0);
			trace = new LinkedList<>();
			if (dp == 1) {
				trace(0, 0, 1);
				color = new int[n];
				for (int i = 0; i < n; i++) {
					if (color[i] == 0) {
						int x = trace.poll();
						if (x == 0) {
							if (n1 > 0) {
								color[i] = 1;
								n1--;
							} else {
								color[i] = 3;
								n3--;
							}
						} else {
							color[i] = 2;
						}
						color(i);
					}
				}
				pw.println("YES");
				for (int x : color)
					pw.print(x);
				pw.println();
			} else
				pw.println("NO");
		} else
			pw.println("NO");

		pw.flush();
		pw.close();
	}

	static void color(int u) {
		Queue<Integer> q = new LinkedList<>();
		q.add(u);
		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int v : adjList[cur]) {
				if (color[v] == 0) {
					if (color[cur] == 2) {
						if (n1 > 0) {
							color[v] = 1;
							n1--;
						} else {
							color[v] = 3;
							n3--;
						}
						q.add(v);
					} else {
						color[v] = 2;
						q.add(v);
					}
				}
			}
		}
	}

	static boolean f, vis[];
	static int[] color;
	static pair sum;
	static int[][] memo;
	static int n1, n2, n3;
	static ArrayList<pair> arr;
	static Queue<Integer> trace;

	static int dp(int idx, int c) {
		if (idx == arr.size())
			return c == n2 ? 1 : 0;
		if (memo[idx][c] != -1)
			return memo[idx][c];
		int t = dp(idx + 1, c + arr.get(idx).x);
		int l = dp(idx + 1, c + arr.get(idx).y);
		
		return memo[idx][c] = Math.max(t, l);
	}

	static void trace(int idx, int c, int ans) {
		if (idx == arr.size())
			return;
		if (ans == dp(idx + 1, c + arr.get(idx).x)) {
			trace.add(0);
			trace(idx + 1, c + arr.get(idx).x, ans);
		} else {
			trace.add(1);
			trace(idx + 1, c + arr.get(idx).y, ans);
		}
	}

	static boolean isBipartite(int u) {
		Queue<Integer> q = new LinkedList<>();
		color[u] = 1;
		int c1 = 1;
		int c0 = 0;
		vis[u] = true;
		q.add(u);
		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int v : adjList[cur]) {
				if (!vis[v]) {
					color[v] = 1 - color[cur];
					vis[v] = true;
					c1 += color[v] == 1 ? 1 : 0;
					c0 += color[v] == 0 ? 1 : 0;
					q.add(v);
				} else if (color[v] == color[cur])
					return false;
			}
		}
		sum = new pair(c0, c1);
		return true;
	}

	boolean isBipartite(int G[][], int src) {
		// Create a color array to store
		// colors assigned to all veritces.
		// Vertex number is used as index
		// in this array. The value '-1'
		// of colorArr[i] is used to indicate
		// that no color is assigned
		// to vertex 'i'. The value 1 is
		// used to indicate first color
		// is assigned and value 0 indicates
		// second color is assigned.
		int colorArr[] = new int[V];
		for (int i = 0; i < V; ++i)
			colorArr[i] = -1;

		// Assign first color to source
		colorArr[src] = 1;

		// Create a queue (FIFO) of vertex numbers
		// and enqueue source vertex for BFS traversal
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.add(src);

		// Run while there are vertices in queue (Similar to BFS)
		while (q.size() != 0) {
			// Dequeue a vertex from queue
			int u = q.poll();

			// Return false if there is a self-loop
			if (G[u][u] == 1)
				return false;

			// Find all non-colored adjacent vertices
			for (int v = 0; v < V; ++v) {
				// An edge from u to v exists
				// and destination v is not colored
				if (G[u][v] == 1 && colorArr[v] == -1) {
					// Assign alternate color to this adjacent v of u
					colorArr[v] = 1 - colorArr[u];
					q.add(v);
				}

				// An edge from u to v exists and destination
				// v is colored with same color as u
				else if (G[u][v] == 1 && colorArr[v] == colorArr[u])
					return false;
			}
		}
		// If we reach here, then all adjacent vertices can
		// be colored with alternate color
		return true;
	}

	static final int INF = (int) 1e9; // don't increase, avoid overflow
	static ArrayList<Integer>[] adjList;
//	static ArrayList<Edge>[] adjList;
	static int V;
	static int[] p;

	/*
	 * 1. Dijkstra's Algorithm for SSSP on weighted graphs
	 */
//	static long dijkstra(int S, int T) // O(E log E)
//	{
//		long[] dist = new long[V];
//		p = new int[V];
//		p[0] = -1;
//		Arrays.fill(dist, (long) 1e18);
//		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
//		dist[S] = 0;
//		pq.add(new Edge(S, 0)); // may add more in case of MSSP (Mult-Source)
//		while (!pq.isEmpty()) {
//			Edge cur = pq.remove();
//			if (cur.cost > dist[cur.node]) // lazy deletion
//				continue;
//			if (cur.node == T) // remove if all computations are needed
//				return dist[T];
//			for (Edge nxt : adjList[cur.node])
//				if (cur.cost + nxt.cost < dist[nxt.node]) {
//					pq.add(new Edge(nxt.node, dist[nxt.node] = cur.cost + nxt.cost));
//					p[nxt.node] = cur.node;
//				}
//		}
//		return -1;
//	}

	static class Edge implements Comparable<Edge> {
		int node;
		long cost;

		Edge(int a, long b) {
			node = a;
			cost = b;
		}

		public int compareTo(Edge e) {
			return Long.compare(cost, e.cost);
		}
	}

	static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	// method to return LCM of two numbers
	static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	static double dis(int x, int y, int z, int w) {
		return Math.sqrt((x - z) * (x - z) + (y - w) * (y - w));
	}

	static int[] nxtarr() throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] a = new int[st.countTokens()];
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		return a;
	}

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			if (y == o.y)
				return x - o.x;
			return y - o.y;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return x + " " + y;
		}

	}

	static class triple implements Comparable<triple> {
		int x;
		int y;
		int z;

		public triple(int a, int b, int c) {
			x = a;
			y = b;
			z = c;
		}

		@Override
		public int compareTo(triple o) {
			// TODO Auto-generated method stub
			return x - o.x;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return x + " " + y + " " + z;
		}
	}

}
