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_{t h}$ node is equal $a_i$. If $a_i$ is equal to $-1$ then the in-degree of the $i_{t h}$ 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 <= n, m <= 2000)$, which are the number of nodes and the number of edges.
The second line of input contains $n$ integers, the $i_{t h}$ one is $a_i$ $(-1 <= a_i <= 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 <= u, v <= n)$ $(u eq.not 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.
The given graph in both samples :
After making the graph directed in the first sample :
After making the graph directed in the second sample :
## Input
The first line of input contains two integers $n$ and $m$ $(1 <= n, m <= 2000)$, which are the number of nodes and the number of edges.The second line of input contains $n$ integers, the $i_{t h}$ one is $a_i$ $(-1 <= a_i <= 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 <= u, v <= n)$ $(u eq.not v)$, which means that there is an undirected edge between nodes $u$ and $v$.The graph doesn't contain self-loops or multiple edges.
## Output
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.
[samples]
## Note
The given graph in both samples :After making the graph directed in the first sample :After making the graph directed in the second sample :
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of nodes and edges, respectively.
Let $ A = (a_1, a_2, \dots, a_n) \in (\mathbb{Z} \cup \{-1\})^n $ be the target in-degree vector, where $ a_i = -1 $ means no constraint on node $ i $'s in-degree.
Let $ E = \{ \{u_j, v_j\} \mid j \in \{1, \dots, m\} \} $ be the set of undirected edges (no self-loops, no multiple edges).
**Constraints**
1. $ 1 \leq n, m \leq 2000 $
2. $ -1 \leq a_i \leq m $ for all $ i \in \{1, \dots, n\} $
3. For each edge $ \{u_j, v_j\} \in E $, $ 1 \leq u_j < v_j \leq n $, $ u_j \neq v_j $
**Objective**
Determine if there exists an orientation $ D = \{ (u_j, v_j) \text{ or } (v_j, u_j) \mid j \in \{1, \dots, m\} \} $ of the edges such that for each node $ i \in \{1, \dots, n\} $:
$$
\text{in-deg}_D(i) =
\begin{cases}
a_i & \text{if } a_i \neq -1 \\
\text{any integer} & \text{if } a_i = -1
\end{cases}
$$
If such an orientation exists, output "YES" and the directed edges; otherwise, output "NO".