406475: GYM102419 H In-degree

You are given an undirected graph that contains $$$n$$$ nodes and $$$m$$$ edges, the graph doesn't contain self-loops or multiple edges and it doesn't have to be connected.

You should give a direction for every edge (make the graph directed), so that the in-degree of the $$$i_{th}$$$ node is equal $$$a_i$$$. If $$$a_i$$$ is equal to $$$-1$$$ then the in-degree of the $$$i_{th}$$$ node can be anything.

the in-degree of a node is the number of edges the ends in that node.

Can you solve the problem?

The first line of input contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 2000)$$$, which are the number of nodes and the number of edges.

The second line of input contains $$$n$$$ integers, the $$$i_{th}$$$ one is $$$a_i$$$ $$$(-1 \leq a_i \leq m)$$$, which is the needed in-degree.

When $$$a_i = -1$$$ then this node's in degree can be anything.

For the next $$$m$$$ lines, the input will contain two integers $$$u$$$ and $$$v$$$, $$$(1 \leq u , v \leq n)$$$ $$$(u \neq v)$$$, which means that there is an undirected edge between nodes $$$u$$$ and $$$v$$$.

The graph doesn't contain self-loops or multiple edges.

If there is no answer print NO on a line.

otherwise print YES and print $$$m$$$ lines.

print every edge in a directed order, for example, if you had an edge between nodes $$$a$$$ and $$$b$$$.

If you printed $$$a$$$ $$$b$$$, that means that the edge goes from node $$$a$$$ and ends at node $$$b$$$.

You can print the edges in any order.

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

YES
1 2
3 1
3 2
4 3
5 4

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

YES
1 2
3 1
3 2
4 3
4 5

The given graph in both samples :

After making the graph directed in the first sample :

After making the graph directed in the second sample :