As you have noticed, there are lovely girls in Arpa’s land.

People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crush_{i}. [Image] 

Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.

The game consists of rounds. Assume person x wants to start a round, he calls crush_{x} and says: "Oww...wwf" (the letter w is repeated t times) and cuts off the phone immediately. If t > 1 then crush_{x} calls crush_{crush}_{x} and says: "Oww...wwf" (the letter w is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called the Joon-Joon of the round. There can't be two rounds at the same time.

Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible.

Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crush_{i} = i).


-----Input-----

The first line of input contains integer n (1 ≤ n ≤ 100) — the number of people in Arpa's land.

The second line contains n integers, i-th of them is crush_{i} (1 ≤ crush_{i} ≤ n) — the number of i-th person's crush.


-----Output-----

If there is no t satisfying the condition, print -1. Otherwise print such smallest t.


-----Examples-----
Input
4
2 3 1 4

Output
3

Input
4
4 4 4 4

Output
-1

Input
4
2 1 4 3

Output
1



-----Note-----

In the first sample suppose t = 3. 

If the first person starts some round:

The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1.

The process is similar for the second and the third person.

If the fourth person starts some round:

The fourth person calls himself and says "Owwwf", then he calls himself again and says "Owwf", then he calls himself for another time and says "Owf", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4.

In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.

Difficulty: competition

Starter code:

Solutions:
n = int(input())
w = list(map(int, input().split()))
w = [x-1 for x in w]

ws = sorted(w)
for i in range(n):
	if i != ws[i]:
		print(-1)
		return

a = []
vis = [False] * n
for i in range(n):
	if not vis[i]:
		a.append(0)
		j = i
		while not vis[j]:
			a[-1] += 1
			vis[j] = True
			j = w[j]

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

ans = 1
for i in a:
	if i % 2 == 0:
		i //= 2
	ans = ans // gcd(ans, i) * i
print(ans)


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())
a = list(map(int, input().split()))
if sorted(a) != [i + 1 for i in range(n)]:
    print(-1)
else:
    ans = 1
    used = [0 for i in range(n)]
    for i in range(n):
        if used[i] == 0:
            j = i
            am = 0
            while used[j] == 0:
                am += 1
                used[j] = 1
                j = a[j] - 1
            if am % 2:
                ans = lcm(ans, am)
            else:
                ans = lcm(ans, am // 2)
    print(ans)

3

from fractions import gcd

n = int(input())
def dfs(u, v, nxt, vis):
    if u == v:
        return True
    elif vis[u]:
        return False
    else:
        vis[u] = True
        return dfs(nxt[u], v, nxt, vis)


def size(u, v, nxt):
    if u == v:
        return 1
    return size(nxt[u], v, nxt) + 1


nxt = list(map(int, input().split()))
for i in range(n):
    nxt[i] -= 1

szs = []

for i in range(n):
    if not dfs(nxt[i], i, nxt, [False] * n) and nxt[i] != i:
        print(-1)
        return
    elif nxt[i] == i:
        szs.append(1)
    else:
        szs.append(size(nxt[i], i, nxt))


ans = 1
g = 0
for i in range(n):
    if szs[i] % 2 == 0:
        szs[i] //= 2
    ans = (ans * szs[i]) // gcd(ans, szs[i])

print(ans)



n = int(input())

L = list(map(int, input().split()))

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

if len(set(L)) < n:
    print(-1)
else:
    a = 1

    for i in range(n):
        if L[i] == 0: continue
        u = i
        c = 0
        while L[u] != 0:
            c += 1
            v = L[u] - 1
            L[u] = 0
            u = v

        if c % 2 == 0:
            c //= 2

        a = lcm(a, c)

    print(a)



from fractions import gcd
def dfs(cur, sz):
    used[cur] = True
    v = a[cur]
    if (used[v]):
        return sz + 1
    else:
        return dfs(v, sz + 1)
n = int(input())
def nok(a, b):
    return (a * b) // gcd(a, b)
a = list(map(int, input().split()))
par = [-1] * n
for i in range(len(a)):
    a[i] -= 1
    if par[a[i]] != -1:
        print(-1)
        return
    else:
        par[a[i]] = i
#print(par)
used = [False] * n
curnok = 1
for i in range(n):
    if (not used[i]):
        cur = dfs(i, 0)
        if cur % 2 == 0:
            cur //= 2
        curnok = nok(curnok, cur)
print(curnok)


def gcd(a, b):
    if (a == 0):
        return b
    return gcd(b % a, a)

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
u = [False] * n
ans = 1
for i in range(n):
    if (u[i] == False):
        x = i
        c = 1
        while (True):
            u[x] = True
            if (a[x] == i):
                break
            if (u[a[x]] != False):
                print(-1)
                return
            x = a[x]
            c += 1
        if (c % 2 == 0):
            c //= 2
        ans = ans * c // gcd(ans, c)
print(ans)

from fractions import gcd
def dfs(node):
    if (vis[node] == idd[0]):
        return node
    cycleLen[0] += 1
    vis[node] = idd[0]
    return dfs(crush[node])

n = int(input())
crush = list(map(int, input().split()))
for i in range(n):
    crush[i] -= 1
vis = [0] * n
ans = 10**100
idd = [0]
V = []
for i in range(n):
    idd[0] += 1
    cycleLen = [0]
    if (dfs(i) != i):
        ans = -1
    V.append(cycleLen[0])
V.sort()

def lcm(x, y):
    return x * y // gcd(x, y)

if (ans == -1):
    print(ans)
else:
    ans = 1
    inc = 1
    for item in V:

        mem = {}
        bad = False
        while (True):    
            if (ans % item == 0):
                break
            if (item % 2 == 0 and ans % item == item // 2):
                break
            if (ans % item in mem):
                bad = True
                break
            mem[ans % item] = 1
            ans += inc
        if (bad):
            ans = -1
            break
        inc = lcm(inc, ans)
    print(ans)


gcd = lambda a, b: a if b == 0 else gcd(b, a % b)
n = int(input())
a = [0] + list(map(int, input().split()))
t = 1
for i in range(1, n + 1):
    if i == a[i]: continue
    x = i
    cnt = 1
    while a[x] != i and cnt <= n:
        x = a[x]
        cnt += 1
    if cnt == n + 1:
        print(-1)
        return
    if cnt % 2 == 0:
        cnt //= 2
    t = t * cnt // gcd(t, cnt)
print(t)


def lcm(a, b):
    sum = a + b
    large = a if a > b else b
    small = sum - large
    for i in range(1, small + 1):
        if (large * i) % small == 0:
          return large * i
    return None
            # dfs

n = int(input())
crush = list(map(int, input().split(" ")))
# crush = input().split(" ")
visited = [False] * n
graph_len = []

if sum(crush) != (n * (n + 1)) / 2:
    # not all nodes have incoming edges
    print('-1')
else:
    for i in range(n):
        if visited[i]:
            # visited nodes
            # print('visited already', i)
            continue
        idx = i
        len1 = 0
        while not visited[idx]:
            # not visited nodes
            # print('idx visiting', idx, crush[idx] - 1)
            visited[idx] = True
            idx = crush[idx] - 1  # convert values to zero index
            len1 += 1  # self loops 1. two node loop check
        len1 = (int)(len1/2) if len1%2 == 0 else len1
        if len1 not in graph_len:
            # we ll go for lcm. no point in having duplicates
            graph_len.append(len1)

# find lcm of elements in graph_len
    # print(graph_len)
    n1 = graph_len[0]
    for i in range(1, len(graph_len)):
        n2 = graph_len[i]
        n1 = lcm(n1, n2)
        # print('n1->', n1)
    print(n1)


def gcd(x,y):
    return x if y==0 else gcd(y,x%y)
def lcm(x,y):
    return x//gcd(x,y)*y
def dfs(x,y):
    if(vis[x]):
        return y
    vis[x] = 1
    return dfs(c[x-1],y+1)
n =int(input())
c = []
for x in input().split():
    c.append(int(x))
vis = [0]*(n+1)
ind = [0]*(n+1)
for i in range(n):
    ind[i+1]+=1
    ind[c[i]]+=1
mk = 1
for i in range(n):
    if(ind[i+1]&1):
        mk = 0
ans = 1
if(mk):
    for i in range(n):
        if(vis[i+1]==0):
            val = dfs(i+1,0)
        if(val%2==0):
            val//=2
        ans = lcm(ans,val)
    print(ans)
else:
    print("-1");



from math import *
n=int(input())
a=list([int(s)-1 for s in input().split()])
seen=[0]*n
ans=1
lcm=1
for i in range(n):
        if not seen[i]:
                j=i
                leng=0
                while not seen[j]:
                        seen[j]=1
                        leng+=1
                        j=a[j]
                if i==j:
                        if leng%2==0:
                                leng//=2
                        lcm = lcm // gcd(lcm,leng) * leng
                else:
                        ans=-1
                        break
if ans==-1:
        print(-1)
else:
        print(lcm)


from math import gcd
n=int(input())
a=list([int(s)-1 for s in input().split()])
seen=[0]*n
ans=1
lcm=1
for i in range(n):
        if not seen[i]:
                j=i
                leng=0
                while not seen[j]:
                        seen[j]=1
                        leng+=1
                        j=a[j]
                if i==j:
                        if leng%2==0:
                                leng//=2
                        lcm = lcm // gcd(lcm,leng) * leng
                else:
                        ans=-1
                        break
if ans==-1:
        print(-1)
else:
        print(lcm)


from math import gcd as __gcd
n=int(input())
a=list([int(s)-1 for s in input().split()])
seen=[0]*n
ans=1
lcm=1
for i in range(n):
        if not seen[i]:
                j=i
                leng=0
                while not seen[j]:
                        seen[j]=1
                        leng+=1
                        j=a[j]
                if i==j:
                        if leng%2==0:
                                leng//=2
                        lcm = lcm // __gcd(lcm,leng) * leng
                else:
                        ans=-1
                        break
if ans==-1:
        print(-1)
else:
        print(lcm)



import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n=int(input())

l=list([int(x)-1 for x in input().split()])

use=[]
valid=1
for i in range(n):
    t=i
    for j in range(n+5):
        t=l[t]
        if t==i:
            if (j+1)%2==0: use.append((j+1)//2)
            else: use.append(j+1)
            break
    else:
        valid=0

if not valid: print("-1")
else:
    # get lcm
    ans=1
    for i in use:
        t=ans
        while ans%i:
            ans+=t
    print(ans)


def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return int(a * b / gcd(a, b))
    
def run(n, crush):
    visited = [False] * n
    cycle_size = 1
    
    for i in range(0, n):
        if visited[i]:
            continue
        x = i
        c = 0
        while (not visited[x]):
            visited[x] = True
            x = crush[x] - 1
            c += 1
        if x != i:
            return -1
            
        if c % 2 == 0:
            c /= 2
        cycle_size = lcm(cycle_size, c)
    
    return cycle_size
    
n = int(input())
crush = [int(x) for x in input().split()]
print(run(n,crush))


input()
crush = [0] + [int(x) for x in input().split()]
visited = set()

circle_sizes = []

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def lcm(a, b):
    return a * b // gcd(a, b)

def solve():
    for i in range(len(crush)):
        if i not in visited:
            start, cur, count = i, i, 0
            while cur not in visited:
                visited.add(cur)
                count += 1
                cur = crush[cur]
            if cur != start:
                return -1
            circle_sizes.append(count if count % 2 else count // 2)
    
    if len(circle_sizes) == 1:
        return circle_sizes[0]
    
    ans = lcm(circle_sizes[0], circle_sizes[1])
    for size in circle_sizes[2:]:
        ans = lcm(ans, size)
    return ans

print(solve())


def make_function(n, crushes):
    def f(original_node):
        node = original_node
        x = 0
        for i in range(n):
            node = crushes[node]
            x += 1
            if node == original_node:
                break
        else:
            return -1
        return x / 2 if x % 2 == 0 else x
    return f


def lcd(numbers):
    gcd = lambda x, y: int(x) if y == 0 else int(gcd(y, x % y))
    ret = 1
    for number in numbers:
        ret = ret * number / gcd(ret, number)
    return ret


def main():
    n = int(input())
    a = list(map(int, input().split()))
    crushes = {i: x for i, x in zip(list(range(1, n+1)), a)}
    f = make_function(n, crushes)
    numbers = list(map(int, list(map(f, crushes))))
    if -1 in numbers:
        print(-1)
        return
    print(int(lcd(numbers)))


main()


from fractions import gcd

def lcm(a, b):
    return (a * b) // gcd(a, b)

n = int(input())
go = list(map(int, input().split()))
for i in range(n):
    go[i] -= 1
vis = [False for i in range(n)]
ans = 1
for i in range(n):
    vis = [False for j in range(n)]
    x = go[i]
    while True:
        if vis[x] == True:
            break
        vis[x] = True
        x = go[x]
    if vis[i] == False:
        print("-1")
        return
vis = [False for i in range(n)]
for i in range(n):
    if vis[i] == True:
        continue
    x = i
    cycle = 0
    while True:
        if vis[x] == True:
            break
        cycle += 1
        vis[x] = True
        x = go[x]
    if cycle % 2 == 1:
        ans = lcm(ans, cycle)
    else:
        ans = lcm(ans, cycle // 2)
print(ans)


from fractions import gcd
def lcm(l):
    v = 1
    for li in l:
        v = v * li // gcd(v, li)
    return v
n, c = int(input()), [0] + list(map(int, input().split()))
f, l = [False] * (n + 1), []
for i in range(1, n + 1):
    if not f[i]:
        li, x = 0, i
        while not f[x]:
            f[x] = True
            x, li = c[x], li + 1
        if x != i:
            print(-1)
            return
        l.append(li if li % 2 else li // 2)
print(lcm(l))

import math

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def solve():
    
    n=int(input())
    ar=list(map(int,input().split()))
    ar=[0,]+ar
    mark=[0]*(n+1)

    ans=list()
    for i in range(1,n+1):

        if mark[i]==0:
            start=i
            ver=i
            count=0
            while mark[ver]==0:
                mark[ver]=1
                ver=ar[ver]
                count=count+1
            if ver==start:
                if count%2==0:
                    ans=ans+[count//2]
                else:
                    ans=ans+[count]
            else:
                print(-1)
                return 


    f=1
    for x in ans:
        f=f*x//gcd(f,x)
    print(f)

solve()


#from collections import deque
from functools import reduce

n = int(input())
crush = [int(i) - 1 for i in input().split()]

def parity_treat(n):
    if n%2 == 0:
        return n//2
    else:
        return n

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def lcm(a,b):
    return a * b // gcd(a,b)

def lcmm(*args):
    return reduce(lcm, args)


if len(set(crush)) < n:
    print(-1)
else:
    component_size = []
    visited = set()
    for i in range(n):
        if i not in visited:
            tmp = 1
            start = i
            visited.add(start)
            j = crush[start]
            while j !=  start:
                visited.add(j)
                j = crush[j]
                tmp+=1
            component_size.append(tmp)
    component_size = [parity_treat(i) for i in component_size]
    print(lcmm(*component_size))

from math import gcd

n = int(input())
crush = list(map(int,input().split()))
crush = [0] + crush

vis,dis,cyc,flag = [0]*(n+1), [-1]*(n+1),  [], 1

def dfs(u,d):
 	dis[u] = d
 	vis[u] = 1
 	nonlocal flag
 	v = crush[u]
 	if vis[v]==0:
 		dfs(v,d+1)
 	else:
 		if dis[v]==1:
 			cyc.append(d)
 		else:
 			flag = 0
 	dis[u] = -1

for i in range(1,n+1):
	if not flag:
		break
	if vis[i]==0:
		dfs(i,1)



if not flag or len(cyc)==0:
	print(-1)
else:
	def lcm(a,b):
		return a*b//gcd(a,b)

	L = cyc[0] 
	if not L%2:
		L //= 2
	for i in range(1,len(cyc)):
		s = cyc[i]
		if not s%2:
			s //= 2
		L = lcm(L,s)
	print(L)


#  C:\Users\Usuario\HOME2\Programacion\ACM


gcd = lambda a, b: a if b == 0 else gcd(b, a % b)
n = int(input())
a = [0] + list(map(int, input().split()))
t = 1
for i in range(1, n + 1):
    if i == a[i]: continue
    x = i
    cnt = 1
    while a[x] != i and cnt <= n:
        x = a[x]
        cnt += 1
    if cnt == n + 1:
        print(-1)
        return
    if cnt % 2 == 0:
        cnt //= 2
    t = t * cnt // gcd(t, cnt)
print(t)

from math import gcd


def main():
    bb = [-1] * int(input())
    aa = [int(s) - 1 for s in input().split()]
    for b, a in enumerate(aa):
        if bb[a] != -1:
            print(-1)
            return
        bb[a] = b
    cc = set()
    for a, b in enumerate(bb):
        if b != -1:
            c = 0
            while bb[a] != -1:
                bb[a] = -1
                c += 1
                a = aa[a]
        cc.add(c)
    r = 1
    for c in cc:
        c //= 2 - c % 2
        r = r * c // gcd(r, c)
    print(r)


def __starting_point():
    main()

__starting_point()

from math import gcd
def count(x,a,n):
        c=0
        t=x
        while(1):
                x=a[x-1]
                c+=1
                if t==x:
                        #print(t,x)
                        break
                if c>=n:
                        return 0
                        break
        if c%2==0:
                return c//2
        else:
                return c
def xyz():
        n=int(input())
        a=[int(i) for i in input().split()]
        l=1
        for i in range(n):
                p=count(i+1,a,n)
                if p==0:
                        return -1
                l=(p*l)//(gcd(p,l))
        return l
print(xyz())