Problem B
Colourful Graph

Consider an undirected graph on $n$ vertices. A $k$-colouring of the graph is simply an assignment to each vertex one of the $k$ colours. There are no other restrictions – two vertices can get the same colour even if they are connected by an edge.

You are given two $k$-colourings $s$ and $t$. You want to transform from the initial colouring $s$ to the final colouring $t$ step by step. In each step, each vertex may change its colour to one of its neighbours’ colour, or keep its current colour.

Formally, you are looking for a sequence of $k$-colourings $C_0, C_1, C_2, \dots , C_\ell $ such that $C_0 = s$, $C_\ell = t$, and every $C_ i(x)$ equals either

• $C_{i-1}(x)$; or

• $C_{i-1}(y)$ where $(x, y)$ is an edge in the graph

The input graph is guaranteed to be connected and has no self loops. Determine whether it is possible to construct such a sequence, and output one if there is any. The sequence need not be the shortest as long as it uses at most $20\, 000$ steps.

For example, suppose you need to start with the initial colouring on the left and end up with the final colouring on the right:

One solution is as follows:

Input

The first line of input contains three integers $n$, $m$, and $k$. Here $n$ is the number of vertices, $m$ is the number of edges and $k$ is the number of colours ($1 \leq n, k \leq 100$, $0 \leq m \leq {n \choose 2}$). The second line of input contains $n$ integers, each in the range $[0, k-1]$. They indicate the initial colouring. The third line of input contains $n$ integers, each in the range $[0, k-1]$. They indicate the final colouring. Each of the following $m$ lines contains two integers $x_ i$ and $y_ i$, representing an edge in the graph ($1 \leq x_ i, y_ i \leq n$).

The input graph is connected. There are no self loops or multiple edges.

Output

Output Impossible if there is no such sequence. Otherwise, output one or more lines describing a sequence of colouring $C_0, C_1, C_2, \dots , C_\ell $ ($\ell \leq 20\, 000$). Each line contains $n$ integers separated by a single space, describing the colouring. The first line indicates the initial colouring and the last line indicates the final colouring.

You can use at most $20\, 000$ steps, therefore the output contains at most $20\, 001$ lines.

6 6 2
0 1 0 1 1 1
1 0 0 0 1 0
1 2
2 3
3 5
5 4
4 6
6 5

0 1 0 1 1 1
1 1 0 1 0 1
1 1 0 0 1 0
1 0 0 0 1 0

1 0 2
0
1

Impossible