{"raw_statement":[{"iden":"statement","content":"You have a grid of 2 rows and c columns where n cells in the grid are colored black. A black colored cell is adjacent to another black colored cell if they share an edge in the up, down, left, or right direction.\n\nAll black cells in the grid are initially connected as *one* component. You then assign unique indices from 1 to n randomly to all the black cells, and draw an undirected graph that connects two indices of black cells if they were adjacent in the original grid.\n\nUnfortunately, after drawing the graph, you lost the original grid. Given the drawn graph, build and color a new grid of 2 rows and c columns with n black cells, and assign the unique indices from 1 to n to the black cells such that we can build the same given graph from this grid.\n\nThe first line of input contains three integers c, n and e (1 ≤ c ≤ 105, 1 ≤ n ≤ 2 × c, e ≥ n - 1), the number of columns, the number of black cells, and the number of edges in the graph.\n\nEach of the following e lines contains two space-separated integers u and v (1 ≤ u, v ≤ n), representing an edge between two black cells with indices u and v.\n\nIt is guaranteed that the given graph is constructed in the described method and doesn't contain loops or multiple edges.\n\nPrint two lines, each with c integers, representing the constructed grid. Each black cell should contain a distinct number from 1 to n, other cells should contain 0.\n\nIf there is more than one solution, output any of them.\n\n"},{"iden":"input","content":"The first line of input contains three integers c, n and e (1 ≤ c ≤ 105, 1 ≤ n ≤ 2 × c, e ≥ n - 1), the number of columns, the number of black cells, and the number of edges in the graph.Each of the following e lines contains two space-separated integers u and v (1 ≤ u, v ≤ n), representing an edge between two black cells with indices u and v.It is guaranteed that the given graph is constructed in the described method and doesn't contain loops or multiple edges."},{"iden":"output","content":"Print two lines, each with c integers, representing the constructed grid. Each black cell should contain a distinct number from 1 to n, other cells should contain 0.If there is more than one solution, output any of them."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ c, n, e \\in \\mathbb{Z}^+ $ with $ 1 \\leq c \\leq 10^5 $, $ 1 \\leq n \\leq 2c $, $ e \\geq n - 1 $.  \nLet $ G = (V, E) $ be an undirected graph with $ V = \\{1, 2, \\dots, n\\} $ and $ |E| = e $, representing the adjacency relations among black cells.  \n\n**Constraints**  \n1. $ G $ is connected and acyclic or has cycles, but is guaranteed to be realizable as a grid graph on a $ 2 \\times c $ grid.  \n2. Each vertex in $ G $ corresponds to a unique black cell in the grid.  \n3. Two vertices $ u, v \\in V $ are adjacent in $ G $ if and only if their corresponding black cells in the grid share an edge (up/down/left/right).  \n\n**Objective**  \nConstruct a $ 2 \\times c $ grid $ M $, where:  \n- Each cell is either 0 (white) or a unique integer from $ \\{1, 2, \\dots, n\\} $ (black).  \n- Exactly $ n $ cells are colored black.  \n- The adjacency graph induced by black cells in $ M $ (via 4-directional connectivity) is isomorphic to $ G $.  \n\nOutput $ M $ as two rows of $ c $ integers each.","simple_statement":"You are given a graph with n nodes and e edges. The graph came from a 2-row grid where n black cells are connected by adjacency (up/down/left/right). You lost the grid, but have the graph.\n\nRebuild a 2×c grid with n black cells (each labeled 1 to n) and the rest 0, so that two black cells are adjacent in the grid if and only if they are connected by an edge in the graph.\n\nPrint the two rows of the grid.","has_page_source":false}