Artsem has a friend Saunders from University of Chicago. Saunders presented him with the following problem.

Let [n] denote the set {1, ..., n}. We will also write f: [x] → [y] when a function f is defined in integer points 1, ..., x, and all its values are integers from 1 to y.

Now then, you are given a function f: [n] → [n]. Your task is to find a positive integer m, and two functions g: [n] → [m], h: [m] → [n], such that g(h(x)) = x for all $x \in [ m ]$, and h(g(x)) = f(x) for all $x \in [ n ]$, or determine that finding these is impossible.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5).

The second line contains n space-separated integers — values f(1), ..., f(n) (1 ≤ f(i) ≤ n).


-----Output-----

If there is no answer, print one integer -1.

Otherwise, on the first line print the number m (1 ≤ m ≤ 10^6). On the second line print n numbers g(1), ..., g(n). On the third line print m numbers h(1), ..., h(m).

If there are several correct answers, you may output any of them. It is guaranteed that if a valid answer exists, then there is an answer satisfying the above restrictions.


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

Output
3
1 2 3
1 2 3

Input
3
2 2 2

Output
1
1 1 1
2

Input
2
2 1

Output
-1

Difficulty: competition

Starter code:

Solutions:
n = int(input())
f = [int(x) - 1 for x in input().split()]
p = [-1] * n
g = [0] * n
h = [0] * n
m = 0
for i in range(n):
    if f[i] == i:
        p[i] = m
        h[m] = i + 1
        m += 1

h = h[:m]

for i in range(n):
    if p[f[i]] == -1:
        print(-1)
        return
    g[i] = p[f[i]] + 1

print(m)
print(" ".join([str(x) for x in g]))
print(" ".join([str(x) for x in h]))



def main():
	n = int(input())
	ar = []
	fi_values = map(int, input().strip().split())
	groups = dict()
	for i, fi in enumerate(fi_values):
		if fi not in groups:
			groups[fi] = []
		groups[fi].append(i+1)

	g = [0] * n
	h = []
	for k, v in groups.items():
		if k not in v:
			print(-1)
			return

		else:
			h.append(k)
			for i in v:
				g[i-1] = len(h)

	print(len(h))
	print(" ".join(map(str, g)))
	print(" ".join(map(str, h)))

main()

import sys

n = int(input())

f = [int(x) for x in input().split(' ')]

image = set()

h = []

for i, x in enumerate(f):
	if x not in image:
		image.add(x)
		h.append(x)

inv_h = [None for _ in range(n+1)]

for i, x in enumerate(h, 1):
	inv_h[x] = i

for val in h:
	if f[val-1] != val:
		print(-1)
		return

print(len(h))

g = [None for _ in range(n)]

for i in range(n):
	g[i] = inv_h[f[i]]

for x in g:
	print(x, end=' ')
print('')

for x in h:
	print(x, end=' ')
print('')






n = int(input())
f = [None] + list(map(int, input().split(' ')))
invalid = False

g = [None] + [0] * n
h = [None]
x_is_f_which = [None] + [0] * n
m = 0
vis = [None] + [False] * n

for i in range(1, n + 1):
    x = f[i]
    if f[x] != x:
        invalid = True
        break
    if not vis[x]:
        vis[x] = True
        m = m + 1
        h.append(x)
        x_is_f_which[x] = m

if invalid:
    print('-1')
else:
    for i in range(1, n + 1):
        g[i] = x_is_f_which[f[i]]
    print(m)
    def print_list(l):
        print(' '.join(list(map(str, l[1:]))))
    print_list(g)
    print_list(h)



n = int(input())
line = list(map(int, input().split()))
h = []
sets = set()
mm = dict()
out = False
for i in range(len(line)):
    element = line[i]
    if line[element - 1] != element:
        print(-1)
        out = True
        break
    else:
        if element not in sets:
            h += [element]
            mm[element] = len(h) - 1
            sets.add(element)
if not out:
    g = []
    for i in range(n):
        element = line[i]
        index = mm[element]
        g += [index + 1]
    if not out:
        print(len(h))
        print(" ".join(map(str, g)))
        print(" ".join(map(str, h)))


import sys
from collections import defaultdict

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    n = int(input())
    f = [int(i) for i in input().split()]
    inv = defaultdict(set)

    for i, y in enumerate(f, start=1):
        inv[y].add(i)

    # debug(inv, locals())
    m = len(inv)
    g = [0] * (n + 1)
    h = [0] * (m + 1)

    for i, x in enumerate(inv, start=1):
        if x not in inv[x]:
            print(-1)
            return

        for a in inv[x]:
            g[a] = i

        h[i] = x

    print(m)
    print(*g[1:])
    print(*h[1:])

def __starting_point():
    solve()
__starting_point()

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    a = list([x-1 for x in LI()])
    g = [-1] * n
    h = list(set(a))
    l = len(h)
    d = {}
    for i in range(l):
        hi = h[i]
        g[hi] = i
    for i in range(n):
        if g[i] == -1:
            g[i] = g[a[i]]
        elif g[i] != g[a[i]]:
            return -1
    print(l)
    print(' '.join([str(x+1) for x in g]))
    return ' '.join([str(x+1) for x in h])


print(main())


import bisect

n = int(input())
f = [0] + list(map(int, input().split()))
possible = True
for x in range(1, n + 1):
    if f[f[x]] != f[x]:
        possible = False
        break
if possible:
    h = sorted(set(f))
    g = [0]
    for x in range(1, n+1):
        # g.append(h.index(f[x]))
        g.append(bisect.bisect_left(h, f[x]))
    print(len(h) - 1)
    print(*g[1:])
    print(*h[1:])
else:
    print(-1)


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

vis = set()
same = set()
for i in range(1, n+1):
    vis.add(f[i])
    if f[i] == i:
        same.add(f[i])
if len(vis) > len(same):
    print(-1)
    quit()

m = len(same)
same = [0] + list(same)
g = [0 for i in range(n+1)]
h = [0 for i in range(m+1)]
for i in range(1, m+1):
    h[i] = same[i]
    g[same[i]] = i
for i in range(1, n+1):
    g[i] = g[f[i]]

print(m)
print(*g[1:], sep=' ')
print(*h[1:], sep=' ')

n = int(input())
a = list(map(int, input().split()))
i = 0
h = dict()
g = []
for x in a:
    cur = x
    if a[cur - 1] != cur:
        print("-1")
        quit()
    if not h.__contains__(cur):
        h[cur] = len(g)
        g.append(cur)
print(len(g))
for x in a:
    print(h[x] + 1, end=" ")
print()
for x in g:
    print(x, end=" ")


a = int(input())
b = list(map(int,input().split()))
count = 1
s = set()
d = list()
f = dict()
suc = list()
succ = True
for i in b:
    if i in f:
        d.append(f[i])
    else:
        f[i] = count
        suc.append(i)
        d.append(count)
        count+=1
for i in range(len(suc)):
    if d[suc[i]-1] != i+1:
        print(-1)
        return
print(count-1)
print(*d)
print(*suc)

n = int(input())
f = [y for y in map(int, input().split())]

im_f = list(set(f))
ok = True
for y in im_f:
    index = y - 1
    ok &= f[index] == y

if ok:
    m = len(im_f)
    ind = {}
    for i, y in enumerate(im_f):
        ind[y] = i + 1
    print(m)
    values = []
    for y in f:
        values.append(ind[y])
    print(' '.join(map(str, values)))
    print(' '.join(map(str, im_f)))

else:
    print(-1)





n = int(input())
f = [int(x) - 1 for x in input().split()]
p = [-1] * n
g = [0] * n
h = [0] * n
m = 0
for i in range(n):
    if f[i] == i:
        p[i] = m
        h[m] = i + 1
        m += 1

h = h[:m]

for i in range(n):
    if p[f[i]] == -1:
        print(-1)
        return
    g[i] = p[f[i]] + 1

print(m)
print(" ".join([str(x) for x in g]))
print(" ".join([str(x) for x in h]))

n = int(input())
f = [y for y in map(int, input().split())]

im_f = list(set(f))
flag = True
for y in im_f:
    index = y - 1
    flag &= f[index] == y

if flag:
    m = len(im_f)
    ind = {}
    for i, y in enumerate(im_f):
        ind[y] = i + 1
    print(m)
    values = []
    for y in f:
        values.append(ind[y])
    print(' '.join(map(str, values)))
    print(' '.join(map(str, im_f)))

else:
    print(-1)

import sys

n = int(input())
s = input().split()
a = [int(i) for i in s]
a.insert(0,0)

hash = [0 for i in range(n+1)]
g = [0 for i in range(n+1)]
h = [0 for i in range(n+1)]
index = 1

for i in range(1, n+1):
	if hash[a[i]] == 0:
		if index>n:
			print(-1)
			return
		hash[a[i]]=index
		g[i] = index
		h[index] = a[i]
		index+=1
	else:
		g[i] = hash[a[i]]
		
for i in range(1,index):
	if g[h[i]]!=i:
		print(-1)
		return

print(index-1)
print(' '.join([str(i) for i in g[1:n+1]]))
print(' '.join([str(i) for i in h[1:index]]))

n = int(input())
f = [-1] + list(map(int, input().split()))
g = [-1]*(n+1)
h = [-1]
c = 1
for i in range(1, n+1):
	if(f[i] == i):
		g[i] = c
		h += [i]
		c += 1

hinv = {}
m = len(h)-1
for i in range(1, m+1):
	hinv[h[i]] = i

for i in range(1, n+1):
	if(g[i] == -1):
		try:
			g[i] = hinv[f[i]]
		except:
			print(-1)
			return
print(m)
print(*g[1:])
print(*h[1:])

n = int(input())
f = [-1] + list(map(int, input().split()))
g = [-1]*(n+1)
h = [-1]
c = 1
for i in range(1, n+1):
	if(f[i] == i):
		g[i] = c
		h += [i]
		c += 1

hinv = {}
m = len(h)-1
for i in range(1, m+1):
	hinv[h[i]] = i

for i in range(1, n+1):
	if(g[i] == -1):
		try:
			g[i] = hinv[f[i]]
		except:
			print(-1)
			return
print(m)
print(*g[1:])
print(*h[1:])

n = int(input())
f = list(map(int, input().split()))
h = []
ind_h = [-1] * (n + 1)
g = [0] * n
occs = {}
for i in range(len(f)):
    if f[i] not in occs:
        occs[f[i]] = {i + 1}
        h.append(f[i])
        ind_h[f[i]] = len(h) - 1
        g[i] = len(h)
    else:
        g[i] = ind_h[f[i]] + 1
        occs[f[i]].add(i + 1)
for k in occs:
    if k not in occs[k]:
        print(-1)
        return
print(len(h))
print(*g)
print(*h)


n = int(input())
f = list(map(int,input().split()))
h={}
g=[]
for i in f:
    if f[i-1]!=i:
        print(-1)
        return
    elif i not in h:
        h[i]=len(g)
        g.append(i)
print(len(g))
for i in f:
    print(h[i]+1,end=' ')
print()
print(*g)


n = int(input())
l = list(map(int,input().split()))
a = [0]*n
b = []
c = []
ptr = 1
for i in range(n):
    if(a[l[i]-1]==0):
        c.append(l[i])
        a[l[i] - 1]= ptr
        ptr+=1
    b.append(a[l[i] - 1])
for i in range(n):
    if(c[b[i]-1]!=l[i]):
        print(-1)
        return
for i in range(ptr-1):
    if(b[c[i]-1]-1!=i):
        print(-1)
        return


print(ptr-1)
for i in b: print(i,end = " ")
print()
for i in c:print(i,end = " ")

n = int(input())
l = list(map(int,input().split()))
a = [0]*n
b = []
c = []
ptr = 1
for i in range(n):
    if(a[l[i]-1]==0):
        c.append(l[i])
        a[l[i] - 1]= ptr
        ptr+=1
    b.append(a[l[i] - 1])
for i in range(n):
    if(c[b[i]-1]!=l[i]):
        print(-1)
        return
for i in range(ptr-1):
    if(b[c[i]-1]-1!=i):
        print(-1)
        return


print(ptr-1)
for i in b: print(i,end = " ")
print()
for i in c:print(i,end = " ")