{"problem":{"name":"H. In-degree","description":{"content":"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 ev","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10241H"},"statements":[{"statement_type":"Markdown","content":"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.\n\nYou 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.\n\nthe in-degree of a node is the number of edges the ends in that node.\n\nCan you solve the problem?\n\nThe 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.\n\nThe 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.\n\nWhen $a_i = -1$ then this node's in degree can be anything.\n\nFor 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$.\n\nThe graph doesn't contain self-loops or multiple edges.\n\nIf there is no answer print _NO_ on a line.\n\notherwise print _YES_ and print $m$ lines.\n\nprint every edge in a directed order, for example, if you had an edge between nodes $a$ and $b$.\n\nIf you printed $a$ $b$, that means that the edge goes from node $a$ and ends at node $b$.\n\nYou can print the edges in any order.\n\nThe given graph in both samples :\n\nAfter making the graph directed in the first sample :\n\nAfter making the graph directed in the second sample :\n\n## Input\n\nThe 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.\n\n## Output\n\nIf 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.\n\n[samples]\n\n## Note\n\nThe given graph in both samples :After making the graph directed in the first sample :After making the graph directed in the second sample :","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of nodes and edges, respectively.  \nLet $ 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.  \nLet $ E = \\{ \\{u_j, v_j\\} \\mid j \\in \\{1, \\dots, m\\} \\} $ be the set of undirected edges (no self-loops, no multiple edges).\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 2000 $  \n2. $ -1 \\leq a_i \\leq m $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. For each edge $ \\{u_j, v_j\\} \\in E $, $ 1 \\leq u_j < v_j \\leq n $, $ u_j \\neq v_j $  \n\n**Objective**  \nDetermine 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\\} $:  \n$$\n\\text{in-deg}_D(i) = \n\\begin{cases}\na_i & \\text{if } a_i \\neq -1 \\\\\n\\text{any integer} & \\text{if } a_i = -1\n\\end{cases}\n$$  \nIf such an orientation exists, output \"YES\" and the directed edges; otherwise, output \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10241H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}