Şokolad
Şokolad, hansı ki, "Nəm Nəm" konfet şirkəti tərəfindən istehsal olunur, N kvadratcikdən ibarət 1×N ölçülü plitka şəklindədir. Hər bir kvadratcikdə N məşhur konfet ustasından biri təsvir olunub. Şirkət tərəfindən istehsal olunan müxtəlif şokoladlarda eyni N konfet ustası təsvir olunur, lakin fərqli ardıcıllıqla.
**Tapşırıq.** İki şokolad plitkasında portretlərin verilmiş ardıcıllığı üçün birinci plitkanı neçə ən az hissəyə bölmək lazım olduğunu müəyyən edən proqram yazın ki, onun hissələrini dəyişməklə ikinci plitkanı yaratmaq mümkün olsun. Plitkanı yalnız kvadratciklərin sərhədləri boyunca qırmaq olar, plitkanı və ya onun hissələrini çevirmək olmaz.
**Giriş məlumatları.** Giriş faylının ilk sətiri şokolad plitkasının ölçüsünü, yəni kvadratciklərin sayını təyin edən N (2 ≤ N ≤ 10^5) natural ədədini ehtiva edir. Bütün konfet ustaları 1-dən N-ə qədər nömrələnib. Faylın ikinci və üçüncü sətirləri hər biri N fərqli natural ədəd ehtiva edir (bütün ədədlər N-dən çox deyil) — müvafiq olaraq birinci və ikinci plitkalardakı portretlərin ardıcıllığı. Bu ardıcıllıqların fərqli olduğu məlumdur.
**Çıxış məlumatları.** Çıxış faylına yalnız bir ədəd yazılmalıdır — birinci plitkanı ikinci plitkadakı portretlərin ardıcıllığını əldə etmək üçün hansısa şəkildə dəyişməklə ən az neçə hissəyə bölmək lazım olduğunu göstərən ədəd.
**Qiymətləndirmə.** Test dəsti 4 blokdan ibarətdir, hansı ki, əlavə olaraq aşağıdakı şərtlər yerinə yetirilir:
- 20 bal: 2 ≤ N ≤ 3. - 20 bal: 3 < N ≤ 6. - 30 bal: 6 < N ≤ 1000. - 30 bal: 1000 < N ≤ 10^5.
**İzah.** Birinci plitkanı dörd hissəyə belə bölmək olar: kvadratcik 4, kvadratcik 3, iki kvadratcik 2 və 5, kvadratcik 1. Bu hissələri lazım olan şəkildə dəyişməklə, ikinci plitkadakı portretlərin eyni ardıcıllığını əldə edəcəyik. Eyni zamanda, üç və ya iki hissəyə bölməklə heç bir şəkildə ikinci plitkadakı portretlərin eyni ardıcıllığını əldə etmək mümkün olmayacaq.