405959: GYM102191 J Graph to Grid

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.

All 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.

Unfortunately, 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.

The first line of input contains three integers c, n and e (1 ≤ c ≤ 10⁵, 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.

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.

7 10 10
2 10
7 4
10 3
1 4
3 9
9 6
1 6
5 4
6 8
8 3

2 10 3 8 0 7 0 
0 0 9 6 1 4 5