9151: Grid World

An r×c grid graph is a graph whose vertices correspond to the points in the plane with integer coordinates, $x$-coordinates being in the range $1$, ..., $r$, $y$-coordinates being in the range $1$, ..., $c$, and two vertices are connected by an edge whenever the corresponding points are at distance 1. An r×cr\times cr×c cyclic grid graph is a graph formed by connecting the first row with the last row and the first column with the last column on the basis of the r×cr\times cr×c grid graph. Formally, in a r×cr\times cr×c cyclic grid graph, (x,y)(x,y)(x,y) and (x,ymodc+1)(x, y\bmod c+1)(x,ymodc+1) is adjacent, and (x,y)(x,y)(x,y) and (xmodr+1,y)(x\bmod r+1, y)(xmodr+1,y) is adjacent.

Desprado2 constructed an r×cr\times cr×c grid graph, but unfortunately, there are some broken vertices into the graph. This graph has some properties:

• r, c≥5r,\ c\ge 5r, c≥5.
• Each unbroken vertex is adjacent to at least three unbroken vertices.
• Every row and column has at least four unbroken vertices.
• For any broken vertices $u$ and $v$, if they are not in the same connected component, then the shortest distance between $u$ and $v$ is at least $5$.

Some examples are shown above, where white denotes unbroken vertices while black denotes broken vertices.

•  The graph in (a) is valid.
•  The graph in (b) is invalid, because the shortest distance between broken vertices $(3,3)$ an $(5,5)$ is only 4, which breaks property $4$.
•  The graph in (c) is invalid, because the shortest distance between two broken vertices is 3, which breaks property $4$.
•  The graph in (d) is invalid, because the row $3$ only contains $3$ unbroken vertices, which breaks property 3.
•  The graph in (e) is invalid, because the unbroken vertex $(4,3)$ is adjacent to only two unbroken vertices, which breaks property $2$.

After removing all the broken vertices in the graph and numbering the unbroken vertices arbitrarily, he got an undirected graph of $n$ vertices and $m$ edges. There is an edge between $u$ and $v$ in the undirected graph if and only if $u$ and $v$ are adjacent in the original cyclic grid graph. Unfortunately again, after some days, he only remembered the undirected graph and forgot the coordinates of vertices in the original cyclic grid graph.

Please help Desprado2 to restore the original cyclic grid graph.

The first line contains four integers $n$, $m$, $r$ and $c$ (n≤105, m≤2n, n≤r⋅c≤106n\le 10^5,~ m\le 2n,~ n\le r\cdot c\le 10^6n≤105, m≤2n, n≤r⋅c≤106), denoting the number of vertices and edges in the undirected graph, and the number of rows and columns in the original cyclic grid graph.
Then follows $m$ lines. Each line contains two integers $u$ and $v$ (1≤u,v≤n, u≠v1\le u,v\le n,~ u\ne v1≤u,v≤n, u=v), denoting an edge in the undirected graph.
It is guaranteed that the undirected graph is converted from a valid cyclic grid graph satisfying all the properties in problem description.

Print an r×cr\times cr×c matrix denoting the original cyclic grid graph. The number ai,ja_{i,j}ai,j denotes the vertex ai,ja_{i,j}ai,j in the undirected graph locates at the $i$-th row and $j$-th column in the original cyclic grid graph. If vertex (i,j)(i,j)(i,j) in original cyclic grid graph is broken, then ai,j=−1a_{i,j}=-1ai,j=−1.
Note that there are multiple answers since flipping, shifting and sometimes transposing the matrix do not affect the correctness. You are required to print the following one:
Let
bi,j={ai,jif, ai,j>0r⋅c+1if, ai,j=−1b_{i,j}=\begin{cases} a_{i,j} & \mathrm{if,} \ a_{i,j}>0\\ r\cdot c + 1 & \mathrm{if,} \ a_{i,j}=-1 \end{cases}bi,j={ai,jr⋅c+1if, ai,j>0if, ai,j=−1
You should print the answer such that the sequence (b1,1, b1,2, ⋯, b1,c, b2,1, ⋯, br,c)(b_{1,1},\ b_{1,2},\ \cdots,\ b_{1,c},\ b_{2,1},\ \cdots,\ b_{r,c})(b1,1, b1,2, ⋯, b1,c, b2,1, ⋯, br,c) is lexicographically smallest among all answers.
Please note that if your programming language is $\text{C++}$ and you use $\text{std::cout}$, please use ''$\text{n}$'' instead of $\text{std::endl}$ to insert a new line, because $\text{std::endl}$ will flush the output buffer so it may be too slow.

24 46 5 5
24 23
24 4
4 7
4 14
14 18
14 9
9 10
9 2
2 5
2 24
23 13
23 7
7 3
7 18
18 6
18 10
10 5
5 20
5 23
13 15
13 3
3 12
3 6
6 22
20 19
20 13
15 17
15 12
12 8
12 22
22 11
22 1
1 16
1 19
19 21
19 15
17 24
17 8
8 4
8 11
11 14
11 16
16 9
16 21
21 2
21 17

1 16 9 10 -1
19 21 2 5 20
15 17 24 23 13
12 8 4 7 3
22 11 14 18 6