{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"First 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$."},{"iden":"output","content":"you 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$."},{"iden":"note","content":"First Sample :Before flipping After flipping "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"Given a directed graph with n nodes and m edges, flip some edges (reverse their direction) so that the resulting graph has no cycles. Output a string of length m: '0' if the edge stays the same, '1' if it's flipped.","has_page_source":false}