Pociąg
Limit pamięci: 64 MB
Na pewną bajtocką wyspę co roku trafia duży transport surowców.
Dostarczane są one do portu, skąd dalej rozwożone są
pociągiem do wszystkich miast na całej wyspie.
Miasta znajdują się tylko przy brzegu i są ponumerowane kolejno od do .
Trasa pociągu prowadzi wokół całej wyspy przez wszystkie miasta.
Pociąg składa się z lokomotywy ciągnącej pewną liczbę wagonów.
W każdym wagonie przewożony jest inny rodzaj surowca.
Ponadto, do każdego miasta dostarczany jest inny surowiec.
Wagonów jest dokładnie tyle co miast.
Dotychczas wagony były zawsze tak ustawiane, że pociąg w każdym mieście
odczepiał ostatni wagon i ruszał do następnego miasta. W ten sposób
wykonywał tylko jedno okrążenie. Niestety tym razem surowce zostały źle
oznaczone i pomylono kolejność ustawienia wagonów.
Maszynista zastanawia się, ile minimalnie okrążeń będzie musiał wykonać,
aby rozwieźć wszystkie surowce do odpowiednich miast,
wiedząc, że może zawsze odczepiać tylko ostatni wagon oraz nie może doczepiać
już odczepionych. Stacją początkową i końcową jest miasto numer 1, w
którym również znajduje się port. Nowe okrążenie liczone jest wtedy, gdy
pociąg wyruszy do miasta numer 2.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita
(), oznaczająca liczbę miast położonych na wyspie.
W kolejnym wierszu znajduje się liczb całkowitych
(, dla ), przy czym oznacza rodzaj
surowca znajdującego się w -tym wagonie od lokomotywy.
W kolejnym wierszu znajduje się parami różnych
liczb całkowitych , oznaczających
surowce zamawiane przez miasta o numerach .
Liczby w drugim i trzecim wierszu są pooddzielane pojedynczymi odstępami.
Można założyć, że zbiory liczb oraz są takie same,
tzn. .
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się
jedna liczba całkowita oznaczająca minimalną liczbę okrążeń, które pozwolą
rozwieźć wszystkie surowce do odpowiednich miast.
Przykład
Dla danych wejściowych:
5
1 2 3 4 5
1 3 4 2 5
poprawną odpowiedzią jest:
3
Wyjaśnienie do przykładu:
W pierwszym okrążeniu odczepiony zostaje tylko wagon przewożący surowiec
numer 5, w drugim - wagon przewożący surowiec numer 4, wreszcie w trzecim,
ostatnim okrążeniu odczepione zostają kolejno wagony przewożące surowce
o numerach 3, 2, 1.
Autor zadania: Jacek Tomasiewicz.