Перетасування#3139
Казино володіє дорогою машиною для тасування карт, яка може тасувати до карт за раз (у кожній колоді карти). Для зручності ми позначимо карти як 1, 2, 3, \ldots, N, де — загальна кількість карт, а копії однієї й тієї ж карти (наприклад, туз пік) з різних колод вважаються різними. На жаль, машина для тасування несправна і завжди тасує карти однаково. Компанія, що виробляє ці машини, збанкрутувала внаслідок економічного спаду. Немає кому полагодити машину, а новий пристрій коштує надто дорого.
Як талановитий співробітник казино, ви розумієте, що не все втрачено. Використовуючи машину нуль або більше разів, можна отримати різні варіанти тасування. Наприклад, нехай машина тасує карти 1, 2, 3, 4 у порядок 2, 3, 4, 1. Якщо покласти карти у машину, дістати їх і знову, не змінюючи порядок, вставити, ви отримаєте порядок 3, 4, 1, 2. Таким чином, можна отримати чимало різних перестановок, хоча це може займати більше часу. Однак це не є великою проблемою, оскільки колоди не потрібно тасувати дуже часто, а використані колоди можна тасувати тоді, коли інші використовуються, щоб уникнути простою.
На жаль, не всі перестановки можна отримати таким чином, і ви хочете дізнатися, чи може такий спосіб "зіграти" на користь казино чи гравця. Першим кроком вам потрібно з'ясувати, які перестановки можна отримати, і скільки разів потрібно пропустити колоду через машину, щоб отримати бажану перестановку.
Вхід для кожного випадку складається з трьох рядків. Перший рядок містить одне ціле число — кількість карт для тасування. Це додатне ціле число, не більше . У другому рядку перелічені цілі числа від до у певному порядку через пробіл. Цей список задає порядок, у який машина тасує впорядковані за зростанням карти 1, 2, \ldots, N. Третій рядок у такому ж форматі задає перестановку, яку ви бажаєте отримати. Кінець вхідних даних позначається рядком, у якому N = 0.
Для кожного випадку виведіть мінімальну кількість разів (нуль або більше), яку потрібно пропустити колоду через машину, щоб отримати бажану перестановку. Якщо це неможливо, виведіть "-1". Вихід для кожного випадку повинен складатися з одного рядка. Можете вважати, що відповідь завжди вміщується в -бітове знакове ціле число.
Приклад 1