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 A_i, 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 B_i, 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ż 10¹², 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

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

5