Problem description
Alicja i Bob uwielbiają sztuczki karciane z talią N parami różnych kart (dla uproszczenia oznaczmy je {1, 2, …, N}). Nauczyli się perfekcyjnie tasować karty. W tym przypadku perfekcyjnie oznacza zawsze tak samo. Każde tasowanie Alicji przestawia karty w ustalony sposób, analogicznie każde tasowanie Boba, chociaż tasowanie Alicji i Boba mogą się różnić.
Para postanowiła zaprezentować sztuczkę: mają talię kart ułożoną po kolei (1,2,…,N). Będą wykonywać wiele swoich tasowań na przemian: Alicja, potem Bob, potem Alicja i tak dalej. Chcą aby po wykonaniu serii takich tasowań uzyskać talię ułożoną w dokładnie takiej samej kolejności. Aby pokaz nie był zbyt nudny, chcieliby wykonać jak najmniej tasowań, żeby nie zanudzić publiczności i kiedyś w końcu skończyć sztuczkę. Ile to będzie tych tasowań?
Napisz program, który: wczyta opisy tasowań Alicji i Boba, wyznaczy minimalną liczbę tasowań, niezbędnych do prawidłowego (nie)potasowania talii i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę kart w talii. W drugim wierszu wejścia znajduje się opis tasowania Alicji: ciąg N parami różnych liczb naturalnych Ai, pooddzielanych pojedynczymi odstępami. i-ta liczba oznacza pozycję karty i po tasowaniu. W trzecim wierszu wejścia znajduje się opis tasowania Boba: ciąg N parami różnych liczb naturalnych Bi, pooddzielanych pojedynczymi odstępami. i-ta liczba oznacza pozycję karty i po tasowaniu.
Wyjście
W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę naturalną – minimalną liczbę tasowań, po których talia wraca do układu początkowego.
Jeśli liczba ta miałaby być większa niż 1012, zamiast tego należy wypisać
DUZO.
Ograniczenia
1 ≤ N ≤ 100 000.
W podzadaniu pierwszym za 5 punktów wynik nie przekracza 200.
W podzadaniu drugim za 10 punktów zachodzi N ≤ 10.
W podzadaniu trzecim za 20 punktów wynik jest parzysty.
W podzadaniu czwartym za 65 punktów nie ma dodatkowych ograniczeń.
Przykład
| Wejście | Wyjście | |
|
|