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: MEDIUM_HARD
Tags: Spanning trees

Mathematics

Constructive algorithms

Starter code:

Solutions:
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)
		exit(0)
print(count - 1)
print(*d)
print(*suc)


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(bisect.bisect_left(h, f[x]))
	print(len(h) - 1)
	print(*g[1:])
	print(*h[1:])
else:
	print(-1)


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())


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]))


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)
			exit()
		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)
		exit()
print(index - 1)
print(' '.join([str(i) for i in g[1:n + 1]]))
print(' '.join([str(i) for i in h[1:index]]))


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()


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)
		exit()
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())
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
	elif 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)))


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=' ')


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)
	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()


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 = [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())
a = list(map(int, input().split()))
i = 0
h = {}
g = []
for x in a:
	cur = x
	if a[cur - 1] != cur:
		print(-1)
		break
	if cur not in h:
		h[cur] = len(g)
		g.append(cur)
else:
	print(len(g))
	for x in a:
		print(h[x] + 1, end=' ')
	print()
	for x in g:
		print(x, end=' ')


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())
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)
		exit(0)
for i in range(ptr - 1):
	if b[c[i] - 1] - 1 != i:
		print(-1)
		exit(0)
print(ptr - 1)
for i in b:
	print(i, end=' ')
print()
for i in c:
	print(i, end=' ')


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)
		sys.exit()
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 = list(map(int, input().split()))
h = list(set(f))
if any((f[i - 1] != i for i in h)):
	print(-1)
	exit()
d = [0] * n
for (i, j) in enumerate(h, 1):
	d[j - 1] = i
g = [d[f[i] - 1] for i in range(n)]
print(len(h), ' '.join(map(str, g + h)))


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)