{"problem":{"name":"H. Zuhair and the Dag","description":{"content":"*Memory limit is set to 4 mb.* Kilani has a directed graph with $n$ nodes and $m$ edges, where there could be at most one edge between any pair of nodes, and it contains no self loops. It doesn't hav","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":4096},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10203H"},"statements":[{"statement_type":"Markdown","content":"*Memory limit is set to 4 mb.*\n\nKilani has a directed graph with $n$ nodes and $m$ edges, where there could be at most one edge between any pair of nodes, and it contains no self loops. It doesn't have to be a connected graph.\n\nKilani thinks that Zuhair is a very smart person so he decided to give him a problem on that graph.\n\nZuhair should choose a sub-set of edges and flip them, so if the edges were going from node $u$ to node $v$, it becomes from node $v$ to $u$.\n\nHe should choose a sub-set of edges in order to make the graph a DAG.\n\nD$\"\"_(i r i c t e d)$A$\"\"_(c y c l i c)$G$\"\"_(r a p h)$ is a directed graph without any cycles.\n\nFirst line contains 2 integers $n$ and $m$, which are the number of nodes and the number of edges $(2 <= n <= 10^6)$ $(1 <= m <= 10^6)$. The next $m$ lines , will contains 2 integers for each, $u$ and $v$ $(1 <= u, v <= n)$ $(u eq.not v)$, which means that there is a one way edge goes from node $u$ to node $v$.\n\nyou should print a string with length $m$, the $i_{t h}$ character should be '0' if you want the $i_{t h}$ edge to go from node $u$ to $v$, and '1' to go from $v$ to $u$.\n\nFirst Sample :\n\nBefore flipping \n\nAfter flipping \n\n## Input\n\nFirst line contains 2 integers $n$ and $m$, which are the number of nodes and the number of edges $(2 <= n <= 10^6)$ $(1 <= m <= 10^6)$. The next $m$ lines , will contains 2 integers for each, $u$ and $v$ $(1 <= u, v <= n)$ $(u eq.not v)$, which means that there is a one way edge goes from node $u$ to node $v$.\n\n## Output\n\nyou should print a string with length $m$, the $i_(t h)$ character should be '0' if you want the $i_(t h)$ edge to go from node $u$ to $v$, and '1' to go from $v$ to $u$.\n\n[samples]\n\n## Note\n\nFirst Sample :Before flipping After flipping","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a directed graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $, $ n \\in \\mathbb{Z}^+ $, $ 2 \\leq n \\leq 10^6 $: set of nodes.  \n- $ E = \\{e_1, e_2, \\dots, e_m\\} $, $ m \\in \\mathbb{Z}^+ $, $ 1 \\leq m \\leq 10^6 $: set of directed edges, where each $ e_i = (u_i, v_i) $, $ u_i, v_i \\in V $, $ u_i \\ne v_i $, and no self-loops or multiple edges between same pair.  \n\nLet $ x_i \\in \\{0, 1\\} $ for $ i = 1, \\dots, m $: binary variable indicating whether edge $ e_i $ is flipped:  \n- $ x_i = 0 $: edge remains $ u_i \\to v_i $,  \n- $ x_i = 1 $: edge is flipped to $ v_i \\to u_i $.  \n\nLet $ G' = (V, E') $ be the resulting directed graph after applying flips $ \\{x_i\\} $, where each edge $ e_i $ becomes $ (u_i, v_i) $ if $ x_i = 0 $, or $ (v_i, u_i) $ if $ x_i = 1 $.  \n\n**Constraints**  \n1. $ G' $ must be a DAG: it contains no directed cycles.  \n\n**Objective**  \nFind a binary string $ s = x_1 x_2 \\dots x_m \\in \\{0,1\\}^m $ such that $ G' $ is a DAG.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10203H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}