FRAKTAL - konkurs programistyczny

Dostałeś zadanie przygotować grafik na nocne zmiany w fabryce. Nikt nie lubi pracować w nocy, więc żeby uniknąć wszelkich dyskusji przydzieliłeś pracowników na dyżury po kolei zgodnie z ich numerami pracowniczymi (od 1 do n). Dodatkowo masz do dyspozycji pewną liczbę pracowników kontraktowych, którzy mogą pracować w określone noce.

Przykładowy grafik na kolejne noce wygląda tak:

1 2 0 0 3

0 oznacza pracownika kontraktowego, pozostałe liczby - pracowników firmy.

W ostatniej chwile dostałeś informację, że pracownicy kontraktowi muszą przyjść w inne dni. Przygotowałeś drugi grafik zgodnie z nowymi wytycznymi:

0 1 2 0 3

Teraz musisz powiadomić pracowników firmy o zaistniałej zmianie. Musisz powiadomić tylko tych, dla których nastąpiła zmiana w grafiku. Dodatkowo dzwoniąc po kolei do każdego z nich musisz się upewnić, że kolejność dyżurów pracowników jest cały czas taka sama (pracownik z numerem 10 nie może znaleźć się przed pracownikiem z numerem 9 lub niższym, a także nie może się znaleźć za pracownikiem z numerem 11 i większym).

Na każdym etapie informowania pracowników, porządek dyżurów musi być zachowany!

W powyższym przykładzie należy poinformować o dwóch zmianach. Najpierw musisz poinformować pracownika z numerem 2 o zmianie z drugiego na trzeci dyżur (2 3). A następnie pracownika z numerem 1, że zamiast pojawić się na pierwszej zmianie, będzie pracował na drugiej (1, 2). Jeżeli najpierw powiadomimy pracownika z numerem 1, to otrzymamy nieprawidłowy grafik (2 1 0 0 3), dlatego taka kolejność jest nieprawidłowa.

Porządek dyżurów obowiązuje tylko pracowników firmy. Kolejność dyżurów pracowników kontraktowych nas nie interesuje.

Określ minimalną liczbę telefonów, jakie musisz wykonać oraz podaj kolejne zmiany, o których musisz poinformować pracowników.

Wejście

Na wejściu znajduje się liczba n - ilość dyżurów (n ≤ 2*10⁵).

W kolejnych dwóch liniach znajduje się po n liczb k_i (0 ≤ k_i ≤ n) oznaczających numer pracownika, który będzie pracował na tej zmianie (k_i = 0 dla pracownika kontraktowego, k_i > 0 dla pracownika firmy).

Pierwsza linia zawiera początkowy grafik. Druga linia zawiera nowo otrzymany grafik. Oba wejściowe grafiki są prawidłowe i zawierają tyle samo dyżurów dla pracowników kontraktowych.

Numery pracowników przydzielonych do określonych dni są kolejnymi liczbami naturalnymi (zaczynając od 1). Jeżeli jest 10 dni w grafiku i 4-ech pracowników kontraktowych, to w grafiku pojawią się pracownicy o numerach: 1, 2, 3, 4, 5 i 6.

Wyjście

Na wyjściu należy wypisać ile najmniej zmian należy wykonać, żeby przekształcić pierwszy grafik w drugi.

Następnie należy podać kolejne zmiany między którymi dyżurami należy zamienić przydzielonych do nich pracowników, aby ostatecznie otrzymać nowy grafik.

Dyżury numerujemy wg ich kolejności na wejściu od 1 do n.

Uwaga! Podając kolejne rotacje wypisujemy pozycje w grafiku między którymi dokonujemy zamiany, a nie numery pracowników, którym zmieniamy dyżury. Każda poprawna kolejność zmian będzie zaakceptowana.

5
1 2 0 0 3
0 1 2 0 3

2
2 3
1 2

10
1 2 3 0 0 0 4 5 6 7
0 0 1 2 3 4 5 6 7 0

7
3 5
7 6
4 2
1 3
8 7
9 8
10 9