Problem A
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 $20000$ 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\le n,k\le 100$, $0\le m\le (\genfrac{}{}{0ex}{}{n}{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\le x_i,y_i\le 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 \le 20000$). 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 $20000$ steps, therefore the output contains at most $20001$ 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