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 ≤ 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.
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.
## Input
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.
## Output
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.
[samples]
**Definitions**
Let $ c, n, e \in \mathbb{Z}^+ $ with $ 1 \leq c \leq 10^5 $, $ 1 \leq n \leq 2c $, $ e \geq n - 1 $.
Let $ G = (V, E) $ be an undirected graph with $ V = \{1, 2, \dots, n\} $ and $ |E| = e $, representing the adjacency relations among black cells.
**Constraints**
1. $ G $ is connected and acyclic or has cycles, but is guaranteed to be realizable as a grid graph on a $ 2 \times c $ grid.
2. Each vertex in $ G $ corresponds to a unique black cell in the grid.
3. 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).
**Objective**
Construct a $ 2 \times c $ grid $ M $, where:
- Each cell is either 0 (white) or a unique integer from $ \{1, 2, \dots, n\} $ (black).
- Exactly $ n $ cells are colored black.
- The adjacency graph induced by black cells in $ M $ (via 4-directional connectivity) is isomorphic to $ G $.
Output $ M $ as two rows of $ c $ integers each.