Problem: You are given a connected undirected graph with n vertices and m edges. The vertices are enumerated from 1 to n. 

You are given n integers c1, c2, ..., cn, each of them is between  - n and n, inclusive. It is also guaranteed that the parity of cv equals the parity of degree of vertex v. The degree of a vertex is the number of edges connected to it.

You are to write a weight between  - 2·n2 and 2·n2 (inclusive) on each edge in such a way, that for each vertex v the sum of weights on edges connected to this vertex is equal to cv, or determine that this is impossible.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c1, c2, ..., cn ( - n ≤ ci ≤ n), where ci is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of ci equals the parity of degree of vertex i.

The next m lines describe edges of the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), meaning that the i-th edge connects vertices ai and bi.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

Output

If there is no solution, print "NO".

Otherwise print "YES" and then m lines, the i-th of them is the weight of the i-th edge wi ( - 2·n2 ≤ wi ≤ 2·n2).

Examples

Input

3 3
2 2 2
1 2
2 3
1 3


Output

YES
1
1
1


Input

4 3
-1 0 2 1
1 2
2 3
3 4


Output

YES
-1
1
1


Input

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


Output

YES
3
5
3
-1
-3
5


Input

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


Output

NO

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class D901 {
	
	int n;
	LinkedList<Edge>[] adj;
	long[] c;
	HashMap<Edge,Edge> edges;
	Edge[] edgeArray;
	
	private void solve() throws Exception {
		n = nextInt();
		int m = nextInt();
		
		edgeArray = new Edge[m];
		edges = new HashMap<Edge,Edge>();
		

		c = new long[n];
		for(int i = 0; i < n; i++) c[i] = nextInt();
			
		
		adj = new LinkedList[n];
		for(int i = 0; i < n; i++) adj[i] = new LinkedList<Edge>();
		for(int i = 0; i < m; i++){
			int u = nextInt()-1;
			int v = nextInt()-1;
			Edge e = new Edge(u, v);
			edgeArray[i] = e;
			adj[u].addLast(e);
			adj[v].addLast(e);
			edges.put(e,e);
		}
		
		visited = new boolean[n];
		dfsOddDegree(0);

		
		bfs();
		boolean ok = true;
		if(oddCycle != null){
			dfsBipartite(oddCycle[0]);
			for(int i = 0; i < oddCycle.length; i++) {
				 int u = oddCycle[i];
				 int v = oddCycle[(i+1)%oddCycle.length];
				 Edge e = edges.get(new Edge(u,v));
				 e.add((i%2==0?1L:-1L)*c[oddCycle[0]]/2L); 
			 }
		} else{//bipartite
			dfsBipartite(0);
			if(c[0] != 0L) ok = false; 
		}
		if(ok){
			out.println("YES");
			for(int i = 0; i < m; i++) out.println(edgeArray[i].w);
		}else out.println("NO");
	}
	
	void dfsBipartite(int u){
		visited = new boolean[n];
		visit(u);
	}
	
	void dfs(){
		 visited = new boolean[n];
		 int t = oddCycle.length;
		 for(int i = 0; i < t; i++) visited[oddCycle[i]] = true;
		 for(int i = 0; i < t; i++) visit(oddCycle[i]);
		 long last = 0;
		 for(int i = 0; i < t; i++) {
			 int u = oddCycle[i];
			 int v = oddCycle[(i+1)%t];
			 Edge e = edges.get(new Edge(u,v));
			 last = c[u]/2L-last;
			 e.add(last);			 
		 }
		 last = 0;
		 for(int i = t-1; i > 0; i--) {
			 int u = oddCycle[i];
			 int v = oddCycle[i-1];
			 Edge e = edges.get(new Edge(u,v));
			 last = c[u]/2L-last;
			 e.add(last);			 
		 }
		
	}
	
	boolean[] visited;
	
	void visit(int u){
		visited[u] = true;
		for(Edge e:adj[u]){
			int v = e.other(u);
			if(!visited[v]) {
				visit(v);
				c[u] -= c[v];
				e.add(c[v]);
			}
		}
	}
	
	int[] p;
	
	Integer[] oddCycle;
	
	void bfs(){
		color = new int[n];
		p = new int[n];
		Arrays.fill(color, -1);
		Arrays.fill(p, -1);
		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.addLast(0);
		color[0] = 0;
		while(!queue.isEmpty()){
			int u = queue.removeFirst();
			for(Edge e : adj[u]){
				int v = e.other(u);
				if(color[v] < 0){
					color[v] = 1-color[u];
					p[v] = u;
					queue.addLast(v);
				} else if(color[v] + color[u] != 1){
					oddCycle = oddCycle(u,v);
					return;
				}
			}
		}
	}
	
	Integer[] oddCycle(int u, int v){
		Integer[] pathU = pathToRoot(u);
		Integer[] pathV = pathToRoot(v);
		int idx = 0;
		while(idx < pathU.length && pathU[idx] == pathV[idx]) idx++;
		LinkedList<Integer> cycleList = new LinkedList<Integer>();
		for(int i = idx-1; i < pathU.length; i++) cycleList.addLast(pathU[i]);
		for(int i = pathV.length-1; i >= idx; i--) cycleList.addLast(pathV[i]);
		
		return cycleList.toArray(new Integer[0]);
	}
	
	Integer[] pathToRoot(int u){
		LinkedList<Integer> pathUList = new LinkedList<Integer>();
		while(u >= 0) {
			pathUList.addFirst(u);
			u = p[u];
		}
		return pathUList.toArray(new Integer[0]);
	}
	
	int[] color;
	
	boolean dfsOddDegree(int u){
		visited[u] = true;
		boolean odd = (adj[u].size()%2==1);
		for(Edge e:adj[u]){
			int v = e.other(u);
			if(!visited[v]) {
				boolean nextOdd = dfsOddDegree(v); 
				if(nextOdd)	{
					e.add(1L);
					c[e.u]--;
					c[e.v]--;
				}
				odd = odd ^ nextOdd;
			}
		}
		return odd;
	}

	public static void main(String[] args) {
		new D901().run();
	}

	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer tokenizer;

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private float nextFloat() throws IOException {
		return Float.parseFloat(nextToken());
	}

	private String nextLine() throws IOException {
		return new String(in.readLine());
	}

	private String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(in.readLine());
		}
		return tokenizer.nextToken();
	}
}

class Edge{
	int u;
	int v;
	long w;
	

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + u;
		result = prime * result + v;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Edge other = (Edge) obj;
		if (u != other.u)
			return false;
		if (v != other.v)
			return false;
		return true;
	}

	
	public Edge(int u, int v){
		this.u = Math.min(u, v);
		this.v = Math.max(u, v);
		this.w = 0L;
	}
	
	public int other(int u){
		if(this.u == u) return this.v;
		else return this.u;
	}
	
	public void add(long s){
		this.w += s;
	}
	
	
}