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.