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:

\includegraphics[width=.5\textwidth ]{startend}

One solution is as follows:

\includegraphics[width=.5\textwidth ]{transitions}


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
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 5.6hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in