Some programming contest problems are really tricky: not only do they
require a different output format from what you might have expected, but
also the sample output does not show the difference. For an example,
let us look at permutations.

A permutation of the integers 1 to n is an
ordering of
these integers. So the natural way to represent a permutation is
to list the integers in this order. With n = 5, a
permutation might look like 2, 3, 4, 5, 1. 

However, there is another possibility of representing a permutation:
You create a list of numbers where the i-th number is the
position of the integer i in the permutation. 
Let us call this second
possibility an inverse permutation. The inverse permutation
for the sequence above is 5, 1, 2, 3, 4.

An ambiguous permutation is a permutation which cannot be
distinguished from its inverse permutation. The permutation 1, 4, 3, 2
for example is ambiguous, because its inverse permutation is the same.
To get rid of such annoying sample test cases, you have to write a
program which detects if a given permutation is ambiguous or not.

-----Input Specification-----
The input contains several test cases.

The first line of each test case contains an integer n
(1 ≤ n ≤ 100000).
Then a permutation of the integers 1 to n follows
in the next line. There is exactly one space character
between consecutive integers.
You can assume that every integer between 1 and n
appears exactly once in the permutation.

The last test case is followed by a zero.

-----Output Specification-----
For each test case output whether the permutation is ambiguous or not.
Adhere to the format shown in the sample output.

-----Sample Input-----
4
1 4 3 2
5
2 3 4 5 1
1
1
0

-----Sample Output-----
ambiguous
not ambiguous
ambiguous

Source: codechef | Difficulty: EASY
Tags: Implementation

Constructive algorithms


Solutions:
while True:
	t = int(input())
	if t == 0:
		break
	l = list(map(int, input().split()))
	b = [''] * len(l)
	for i in range(t):
		b[l[i] - 1] = i + 1
	f = 1
	for s in range(t):
		if b[s] != l[s]:
			f = 0
			break
	print('ambiguous' if f else 'not ambiguous')


while int(input()) != 0:
	permutation = list(map(int, input().split()))
	inverse_permutation = [0 for i in range(len(permutation))]
	for index in range(len(permutation)):
		inverse_permutation[permutation[index] - 1] = index + 1
	print('ambiguous') if inverse_permutation == permutation else print('not \xa0\xa0\xa0\xa0\xa0\xa0\xa0\xa0ambiguous')


while True:
	n = int(input())
	if n == 0:
		break
	else:
		permu = list(map(int, input().split()))[:n]
		emp = [0 for x in range(len(permu))]
		for i in range(len(permu)):
			emp[permu[i] - 1] = 1 + i
		if permu == emp:
			print('ambiguous')
		else:
			print('not ambiguous')


t = int(input())
while t != 0:
	l = list(map(int, input().split()))
	l1 = [0] * len(l)
	for i in range(len(l)):
		l1[l[i] - 1] = i + 1
	if l1 == l:
		print('ambiguous')
	else:
		print('not ambiguous')
	t = int(input())


while int(input()) != 0:
	input_nm = [int(i) for i in input().split()]
	ln_f_lst = len(input_nm)
	smpl_lst = [i for i in range(ln_f_lst)]
	empty_lst = [''] * ln_f_lst
	for i in range(1, ln_f_lst + 1):
		empty_lst[input_nm[i - 1] - 1] = i
	print('ambiguous') if input_nm == empty_lst else print('not ambiguous')


while int(input()) != 0:
	l = list(map(int, input().split()))
	ln = len(l)
	ll = [0] * ln
	for i in range(ln):
		k = l[i]
		ll[k - 1] = i + 1
	if l == ll:
		print('ambiguous')
	else:
		print('not ambiguous')


n = int(input())
while n != 0:
	a = list(map(int, input().split()))
	b = a.copy()
	for i in range(n):
		b[a[i] - 1] = i + 1
	if a == b:
		print('ambiguous')
	else:
		print('not ambiguous')
	n = int(input())


while True:
	t = int(input())
	if t == 0:
		break
	permutation = list(map(int, input().split()))
	inverse = [0] * t
	is_ambiguous = True
	for i in range(t):
		inverse[permutation[i] - 1] = i + 1
	for i in range(t):
		if permutation[i] != inverse[i]:
			is_ambiguous = False
			break
	print('ambiguous' if is_ambiguous else 'not ambiguous')


n = int(input())
while n != 0:
	l1 = list(map(int, input().split()))
	l2 = []
	for i in l1:
		l2.append('0')
	for i in range(len(l1)):
		l2[l1[i] - 1] = i + 1
	if l1 == l2:
		print('ambiguous')
	else:
		print('not ambiguous')
	n = int(input())


while True:
	n = int(input())
	if n == 0:
		break
	else:
		abc = list(map(int, input().split()))
		xyz = [0 for i in range(len(abc))]
		pqr = []
		for i in range(n):
			xyz[abc[i] - 1] = i + 1
		if abc == xyz:
			print('ambiguous')
		else:
			print('not ambiguous')


while True:
	n = int(input())
	if n == 0:
		break
	else:
		x = list(map(int, input().split()))
		y = []
		for i in range(n):
			y.append(x[0])
		for i in range(n):
			y[x[i] - 1] = i + 1
	if x == y:
		print('ambiguous')
	else:
		print('not ambiguous')


while True:
	(n, f) = (int(input()), 1)
	if n != 0:
		li = list(map(int, input().split()))
		for i in range(n):
			if li[li[i] - 1] != i + 1:
				f = 0
				break
		print('ambiguous') if f == 1 else print('not ambiguous')
	else:
		break


while int(input()) != 0:
	l = list(map(int, input().split()))
	invArray = [0 for j in range(len(l))]
	for i in range(len(l)):
		invArray[l[i] - 1] = i + 1
	if invArray == l:
		print('ambiguous')
	else:
		print('not ambiguous')


while 1:
	n = int(input())
	if n == 0:
		break
	else:
		l = list(map(int, input().split()[:n]))
		k = []
		for i in range(n):
			k.append(0)
		for j in range(n):
			k[l[j] - 1] = j + 1
		if k == l:
			print('ambiguous')
		else:
			print('not ambiguous')


def invper(ar):
	ar1 = [0] * len(ar)
	for i in range(len(ar)):
		ar1[ar[i] - 1] = i + 1
	return ar1
t = int(input())
while t != 0:
	ar = list(map(int, input().split()))
	ar1 = invper(ar)
	if ar == ar1:
		print('ambiguous')
	else:
		print('not ambiguous')
	t = int(input())


def checker(lst):
	le = len(lst)
	nlst = [0] * le
	for i in range(le):
		nlst[lst[i] - 1] = i + 1
	if nlst == lst:
		print('ambiguous')
	else:
		print('not ambiguous')

def __starting_point():
	while True:
		t = int(input())
		if t == 0:
			return
		else:
			arr = [int(i) for i in input().split()]
			checker(arr)
__starting_point()


while True:
	n = int(input())
	if n == 0:
		break
	l = list(map(int, input().split()))
	l1 = [0] * n
	for i in range(n):
		l1[l[i] - 1] = i + 1
	if l == l1:
		print('ambiguous')
	else:
		print('not ambiguous')


while True:
	(a, b) = (int(input()), 1)
	if a != 0:
		l = list(map(int, input().split()))
		for i in range(a):
			if l[l[i] - 1] != i + 1:
				b = 0
				break
		print('ambiguous' if b == 1 else 'not ambiguous')
	else:
		break


def main():
	while True:
		n = int(input().strip())
		if n == 0:
			break
		a = list(map(int, input().strip().split()))
		b = [0] * n
		for i in range(n):
			b[a[i] - 1] = i + 1
		if a == b:
			print('ambiguous')
		else:
			print('not ambiguous')
main()


ep = int(input())
while ep != 0:
	li = [int(i) for i in input().split()]
	li1 = list('0' * len(li))
	for i in range(len(li)):
		li1[li[i] - 1] = i + 1
	if li == li1:
		print('ambiguous')
	else:
		print('not ambiguous')
	ep = int(input())


def main():
	while True:
		N = int(input().strip())
		if N == 0:
			break
		A = list(map(int, input().strip().split()))
		B = [0] * N
		for j in range(N):
			B[A[j] - 1] = j + 1
		if A == B:
			print('ambiguous')
		else:
			print('not ambiguous')
main()


n = int(input())
while n != 0:
	p = list(map(int, input().split()))
	pinv = [0] * n
	i = 0
	for i in range(n):
		pos = p[i]
		pinv[pos - 1] = i + 1
		i += 1
	if p == pinv:
		print('ambiguous')
	else:
		print('not ambiguous')
	n = int(input())


x = int(input())
while x != 0:
	l = list(map(int, input().split()))
	a = [0] * x
	i = 0
	for i in range(x):
		n = l[i]
		a[n - 1] = i + 1
		i += 1
	if l == a:
		print('ambiguous')
	else:
		print('not ambiguous')
	x = int(input())


t = int(input())
while t:
	l = list(map(int, input().split()))
	k = 10
	for i in range(len(l)):
		if l[l[i] - 1] != i + 1:
			print('not ambiguous')
			k = 1
			break
	if k == 10:
		print('ambiguous')
	t = int(input())


while True:
	n = int(input())
	if not n:
		break
	arr = list(map(int, input().split()))
	brr = [0] * n
	for i in range(n):
		brr[arr[i] - 1] = i + 1
	if arr == brr:
		print('ambiguous')
	else:
		print('not ambiguous')


while True:
	n = int(input())
	if n == 0:
		break
	else:
		m = list(map(int, input().split()))
		m1 = []
		for i in range(len(m)):
			m1.append(0)
		for i in range(len(m)):
			m1[m[i] - 1] = i + 1
	if m == m1:
		print('ambiguous')
	else:
		print('not ambiguous')


while True:
	n = int(input())
	if n == 0:
		break
	a = input().split()
	b = ['0'] * n
	for i in range(n):
		b[int(a[i]) - 1] = str(i + 1)
	if a == b:
		print('ambiguous')
	else:
		print('not ambiguous')


while True:
	n = int(input())
	if n == 0:
		break
	permutations = list(map(int, input().split()))
	inverse_permutation = [0] * n
	for i in range(n):
		inverse_permutation[permutations[i] - 1] = i + 1
	if permutations == inverse_permutation:
		print('ambiguous')
	else:
		print('not ambiguous')


n = int(input())
while n:
	l = list(map(int, input().split()))
	invl = [None] * n
	for j in range(n):
		i = j + 1
		invl[l[j] - 1] = i
	for i in range(n):
		if l[i] != invl[i]:
			print('not ambiguous')
			break
	else:
		print('ambiguous')
	n = int(input())


while True:
	n = int(input())
	if n == 0:
		break
	perm = list(map(int, input().split()))
	inverse_perm = [0] * n
	for i in range(n):
		inverse_perm[perm[i] - 1] = i + 1
	if perm == inverse_perm:
		print('ambiguous')
	else:
		print('not ambiguous')


try:

	def inv(arr):
		arr1 = [0] * len(arr)
		for i in range(len(arr)):
			arr1[arr[i] - 1] = i + 1
		return arr1
	t = int(input())
	while t != 0:
		arr = list(map(int, input().split(' ')))
		arr1 = inv(arr)
		if arr == arr1:
			print('ambiguous')
		else:
			print('not ambiguous')
		t = int(input())
except:
	pass


n = int(input())
while n != 0:
	lst = [int(i) for i in input().strip().split()][0:n]
	dict = {}
	for i in range(1, len(lst) + 1):
		dict[i] = lst[i - 1]
	dict_rev = {}
	for (key, val) in list(dict.items()):
		dict_rev[val] = key
	mykeys = list(dict_rev.keys())
	mykeys.sort(reverse=False)
	lst_rev = []
	for e in mykeys:
		lst_rev.append(dict_rev[e])
	if lst == lst_rev:
		print('ambiguous')
	else:
		print('not ambiguous')
	n = int(input())


while True:
	n = int(input())
	if n == 0:
		break
	else:
		ambiguous = 1
		a = [int(k) for k in input().split()]
		for i in range(0, n):
			if a[i] - 1 >= n or a[i] < 1 or a[a[i] - 1] != i + 1:
				print('not ambiguous')
				ambiguous = 0
				break
		if ambiguous == 1:
			print('ambiguous')


def __starting_point():
	try:
		while int(input()) != 0:
			l = list(map(int, input().split()))
			l1 = [0] * len(l)
			for i in range(len(l)):
				l1[l[i] - 1] = i + 1
			print('ambiguous' if l == l1 else 'not ambiguous')
	except EOFError:
		print('EOFError')
__starting_point()


while 1:
	n = int(input())
	if n == 0:
		break
	else:
		li = list(map(int, input().rstrip().split()))
		l = []
		for i in range(len(li)):
			l.append(0)
		for i in range(len(li)):
			l[li[i] - 1] = i + 1
		if l == li:
			print('ambiguous')
		else:
			print('not ambiguous')


while int(input()) != 0:
	x = list(map(int, input().split()))
	y = len(x)
	length = [0] * y
	for i in range(y):
		k = x[i]
		length[k - 1] = i + 1
	if x == length:
		print('ambiguous')
	else:
		print('not ambiguous')


while True:
	(n, b) = (int(input()), 1)
	if n != 0:
		L = list(map(int, input().split()))
		for i in range(n):
			if L[L[i] - 1] != i + 1:
				b = 0
				break
		if b == 1:
			print('ambiguous')
		else:
			print('not ambiguous')
	else:
		break


while True:
	n = int(input())
	if n == 0:
		break
	else:
		lis1 = list(map(int, input().split()))
		lis2 = []
		for i in range(n):
			lis2.append('')
		for i in range(n):
			lis2[lis1[i] - 1] = i + 1
	if lis1 == lis2:
		print(' ambiguous')
	else:
		print('not ambiguous')


while True:
	n = int(input())
	if n == 0:
		break
	f = 0
	a = [int(x) for x in input().split()]
	for i in range(n):
		if a[a[i] - 1] != i + 1:
			print('not ambiguous')
			f = 1
			break
	if f == 0:
		print('ambiguous')


while True:
	x = int(input())
	if x == 0:
		break
	else:
		y = list(map(int, input().split()))
		z = [0 for i in range(len(y))]
		r = []
		for i in range(x):
			z[y[i] - 1] = i + 1
		if y == z:
			print('ambiguous')
		else:
			print('not ambiguous')