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:
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 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.
Sample Input 1 | Sample Output 1 |
---|---|
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 |
Sample Input 2 | Sample Output 2 |
---|---|
1 0 2 0 1 |
Impossible |