Warsztaty

Limit pamięci: 64 MB

W Bajtocji istnieje tylko jedna droga łącząca wschód z zachodem. Prowadzi ona przez dokładnie miast. W każdym z nich znajduje się warsztat samochodowy umożliwiający przemalowanie samochodu. Każdy z warsztatów ogłosił promocję, w ramach której darmowo przemalowuje samochody z koloru na kolor ( to numer miasta wzdłuż drogi, ). Kolory te są wybierane niezależnie przez każdy warsztat. W każdym warsztacie obowiązuje dokładnie jedna taka promocja. Ze wschodu na zachód wyruszyła wycieczka składająca się z samochodów. Kierowcy w Bajtocji są bardzo oszczędni, ale też lubią odświeżać swoje samochody. Z tego powodu każdy kierowca w każdym kolejnym mieście próbuje przemalować swój samochód, ale robi to tylko wtedy, gdy jest to darmowe. Znając początkowe kolory wszystkich samochodów, chcielibyśmy wyznaczyć kolory tych samochodów po dotarciu na zachód. Należy założyć, że droga jest jednokierunkowa, to znaczy samochody poruszają się tylko ze wschodu na zachód.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , oraz () pooddzielane pojedynczymi odstępami, oznaczające odpowiednio liczbę samochodów, liczbę miast oraz liczbę możliwych kolorów samochodów. Kolory są ponumerowane od do . W drugim wierszu znajduje się liczb całkowitych () pooddzielanych pojedynczymi odstępami i oznaczających kolory kolejnych samochodów. W następnych wierszach znajdują się opisy kolejno odwiedzanych na trasie warsztatów samochodowych. Każdy taki opis składa się z dwóch liczb całkowitych oraz () oddzielonych pojedynczym odstępem, oznaczających, że warsztat w -tym mieście przemalowuje darmowo samochód koloru na kolor .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinno znaleźć się liczb całkowitych, pooddzielanych pojedynczymi odstępami i oznaczających kolory kolejnych samochodów po dotarciu na zachód.

Przykład

Dla danych wejściowych:

5 3 4
1 2 3 4 2
2 4
1 2
4 1

poprawną odpowiedzią jest:

2 1 3 1 1

Wyjaśnienie do przykładu: W pierwszym warsztacie przemalowane zostają samochody drugi i piąty, a zatem sekwencja kolorów przyjmuje postać: 1 4 3 4 4. W drugim warsztacie zmienia się jedynie kolor pierwszego samochodu - nowa sekwencja kolorów to: 2 4 3 4 4. Wreszcie w trzecim warsztacie przemalowane zostają samochody: drugi, czwarty i piąty. Ostateczna sekwencja kolorów to: 2 1 3 1 1.

Autor zadania: Jacek Tomasiewicz.