Considérez un graphe non orienté à $n$ sommets. Un $k$-coloriage du graphe est simplement l'attribution à chaque sommet de l'une des $k$ couleurs. Il n'y a pas d'autres restrictions – deux sommets peuvent recevoir la même couleur même s'ils sont reliés par une arête.
On vous donne deux $k$-coloriages $s$ et $t$. Vous souhaitez passer pas à pas du coloriage initial $s$ au coloriage final $t$. À chaque étape, chaque sommet peut changer sa couleur pour celle de l'un de ses voisins, ou conserver sa couleur actuelle.
Formellement, vous cherchez une suite de $k$-coloriages $C_0, C_1, C_2, \ldots, C_\ell$ telle que $C_0 = s$, $C_\ell = t$, et pour chaque sommet $x$, $C_i(x)$ est égal soit à
• $C_{i-1}(x)$ ; soit à
• $C_{i-1}(y)$ où $(x, y)$ est une arête du graphe
Le graphe donné en entrée est garanti connexe et sans boucle. Déterminez s'il est possible de construire une telle suite, et affichez-en une le cas échéant. La suite n'a pas besoin d'être la plus courte tant qu'elle utilise au plus $20\,000$ étapes.
Par exemple, supposons que vous deviez partir du coloriage initial à gauche et parvenir au coloriage final à droite :
Une solution est la suivante :
Entrée
La première ligne de l'entrée contient trois entiers $n$, $m$ et $k$. Ici, $n$ est le nombre de sommets, $m$ est le nombre d'arêtes et $k$ est le nombre de couleurs ($1 \le n, k \le 100$, $0 \le m \le \binom{n}{2}$). La deuxième ligne de l'entrée contient $n$ entiers, chacun dans l'intervalle $[0, k - 1]$. Ils indiquent le coloriage initial. La troisième ligne de l'entrée contient $n$ entiers, chacun dans l'intervalle $[0, k - 1]$. Ils indiquent le coloriage final. Chacune des $m$ lignes suivantes contient deux entiers $x_i$ et $y_i$, représentant une arête dans le graphe ($1 \le x_i, y_i \le n$).
Le graphe donné en entrée est connexe. Il n'y a ni boucle ni arête multiple.
Sortie
Affichez Impossible s'il n'existe pas de telle suite. Sinon, affichez une ou plusieurs lignes décrivant une suite de coloriages $C_0, C_1, C_2, \ldots, C_\ell$ ($\ell \le 20\,000$). Chaque ligne contient $n$ entiers séparés par un espace, décrivant le coloriage. La première ligne indique le coloriage initial et la dernière ligne indique le coloriage final.
Vous pouvez utiliser au plus $20\,000$ étapes, par conséquent la sortie contient au plus $20\,001$ lignes.
Exemples
Entrée 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
Sortie 1
0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 1 0
Exemples
Entrée 2
1 0 2 0 1
Sortie 2
Impossible
Dans l'Exemple 1, chaque sommet conserve sa couleur précédente ou copie la couleur précédente d'un voisin à chaque transition affichée. Dans l'Exemple 2, l'unique sommet n'a aucun voisin et ne peut pas passer de la couleur $0$ à la couleur $1$.