A tree of size n is an undirected connected graph consisting of n vertices without cycles.

Consider some tree with n vertices. We call a tree invariant relative to permutation p = p1p2... pn, if for any two vertices of the tree u and v the condition holds: "vertices u and v are connected by an edge if and only if vertices pu and pv are connected by an edge".

You are given permutation p of size n. Find some tree size n, invariant relative to the given permutation.

Input

The first line contains number n (1 ≤ n ≤ 105) — the size of the permutation (also equal to the size of the sought tree).

The second line contains permutation pi (1 ≤ pi ≤ n).

Output

If the sought tree does not exist, print "NO" (without the quotes).

Otherwise, print "YES", and then print n - 1 lines, each of which contains two integers — the numbers of vertices connected by an edge of the tree you found. The vertices are numbered from 1, the order of the edges and the order of the vertices within the edges does not matter.

If there are multiple solutions, output any of them.

Examples

Input

4
4 3 2 1


Output

YES
4 1
4 2
1 3


Input

3
3 1 2


Output

NO

Note

In the first sample test a permutation transforms edge (4, 1) into edge (1, 4), edge (4, 2) into edge (1, 3) and edge (1, 3) into edge (4, 2). These edges all appear in the resulting tree.

It can be shown that in the second sample test no tree satisfies the given condition.

Difficulty: HARD
Tags: Greedy algorithms

Tree algorithms

Graph traversal

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def read_data():
	n = int(input())
	ps = list(map(int, input().split()))
	return (n, ps)

def solve(n, ps):
	ps = [p - 1 for p in ps]
	cycles = [0] * n
	roots = []
	has_odd_cycle = False
	for i in range(n):
		if cycles[i] > 0:
			continue
		q = ps[i]
		cycle = 1
		while q != i:
			cycle += 1
			q = ps[q]
		if cycle & 1:
			has_odd_cycle = True
		cycles[i] = cycle
		roots.append(i)
		q = ps[i]
		while q != i:
			cycles[q] = cycle
			q = ps[q]
	mincycle = min(cycles)
	if mincycle > 2:
		return (False, [])
	if mincycle == 1:
		p = cycles.index(1)
		return (True, [(p, i) for i in range(n) if i != p])
	if has_odd_cycle:
		return (False, [])
	p = cycles.index(2)
	q = ps[p]
	edges = [(p, q)]
	for root in roots:
		if root == p or root == q:
			continue
		edges.append((p, root))
		r = ps[root]
		edges.append((q, r))
		r = ps[r]
		while r != root:
			edges.append((p, r))
			r = ps[r]
			edges.append((q, r))
			r = ps[r]
	return (True, edges)
(n, ps) = read_data()
(is_possible, edges) = solve(n, ps)
if is_possible:
	print('YES')
	for (a, b) in edges:
		print(a + 1, b + 1)
else:
	print('NO')


def main():
	n = int(input())
	a = list(map(lambda x: int(x) - 1, input().split()))
	p = -1
	q = -1
	for i in range(n):
		if a[a[i]] == i:
			(p, q) = (i, a[i])
		if a[i] == i:
			print('YES')
			[print(i + 1, j + 1) for j in range(n) if i != j]
			exit()
	if p < 0 or q < 0:
		print('NO')
		exit()
	ans = [(p, q)]
	used = [False] * n
	used[p] = True
	used[q] = True
	for i in range(n):
		if used[i]:
			continue
		ans.append((p, i))
		used[i] = True
		flag = False
		x = a[i]
		while x != i:
			ans.append((p if flag else q, x))
			used[x] = True
			x = a[x]
			flag = not flag
		if not flag:
			print('NO')
			exit()
	print('YES')
	[print(x + 1, y + 1) for (x, y) in ans]
main()


m = int(input())
L = list(map(int, input().split()))
for i in range(len(L)):
	L[i] -= 1
temp = []
d = set()
flag1 = 0
flag2 = 0
flag3 = 0
for (index, num) in enumerate(L):
	if num not in d:
		t = 1
		d.add(num)
		ts = [num]
		while num != index:
			num = L[num]
			d.add(num)
			ts += (num,)
			t += 1
		if t == 1:
			flag1 = 1
			c = num
			break
		elif t == 2:
			flag2 = 1
			c = len(temp)
			a = ts[0]
			b = ts[1]
		elif t % 2 == 1:
			flag3 = 1
		temp.append(ts)
if flag1 == 1:
	print('YES')
	for i in L:
		if not i == c:
			print(i + 1, c + 1)
elif flag2 == 0:
	print('NO')
elif flag3 == 1:
	print('NO')
else:
	print('YES')
	for (index, i) in enumerate(temp):
		if index == c:
			print(i[0] + 1, i[1] + 1)
			continue
		for (index, j) in enumerate(i):
			if index % 2 == 0:
				print(a + 1, j + 1)
			else:
				print(b + 1, j + 1)


n = int(input())
a = [0] + list(map(int, input().split()))
vis = [False] * (n + 1)
lp = []
for i in range(1, n + 1):
	if vis[i]:
		continue
	cur = i
	q = []
	while not vis[cur]:
		vis[cur] = True
		q.append(cur)
		cur = a[cur]
	lp.append(q)
lp.sort(key=len)
res = []

def solve2():
	res.append(tuple(lp[0]))
	for q in lp[1:]:
		if len(q) % 2 == 1:
			print('NO')
			exit()
		for i in range(len(q)):
			res.append((lp[0][i % 2], q[i]))

def solve1():
	for i in range(1, n + 1):
		if i == lp[0][0]:
			continue
		res.append((lp[0][0], i))
if len(lp[0]) >= 3:
	print('NO')
	exit()
if len(lp[0]) >= 2:
	solve2()
else:
	solve1()
print('YES')
for (u, v) in res:
	print(u, v)


n = int(input())
a = list(map(lambda x: int(x) - 1, input().split()))
p = q = -1
for i in range(n):
	if a[a[i]] == i:
		(p, q) = (i, a[i])
	if a[i] == i:
		print('YES')
		[print(i + 1, j + 1) for j in range(n) if i != j]
		exit()
if p < 0 or q < 0:
	print('NO')
	exit()
r = [(p, q)]
v = [0] * n
v[p] = v[q] = 1
for i in range(n):
	if not v[i]:
		r.append((p, i))
		v[i] = 1
		t = 0
		x = a[i]
		while x != i:
			r.append((p if t else q, x))
			v[x] = 1
			t = 1 - t
			x = a[x]
		if not t:
			print('NO')
			exit()
print('YES')
[print(x + 1, y + 1) for (x, y) in r]


import sys
readline = sys.stdin.readline
N = int(readline())
P = list(map(lambda x: int(x) - 1, readline().split()))
PP = []
used = set()
for i in range(N):
	if i not in used:
		res = []
		while i not in used:
			used.add(i)
			res.append(i)
			i = P[i]
		PP.append(res)
if any((len(p) == 1 for p in PP)):
	print('YES')
	for p in PP:
		if len(p) == 1:
			break
	d = p[0]
	Ans = []
	for i in range(N):
		if i != d:
			Ans.append('{} {}'.format(i + 1, d + 1))
	print('\n'.join(Ans))
elif not any((len(p) == 2 for p in PP)):
	print('NO')
elif any((len(p) & 1 for p in PP)):
	print('NO')
else:
	print('YES')
	dd = None
	for p in PP:
		if len(p) == 2:
			dd = p
			PP.remove(p)
			break
	(d1, d2) = dd
	Ans = ['{} {}'.format(d1 + 1, d2 + 1)]
	for p in PP:
		for i in range(len(p)):
			if i & 1:
				Ans.append('{} {}'.format(d1 + 1, p[i] + 1))
			else:
				Ans.append('{} {}'.format(d2 + 1, p[i] + 1))
	print('\n'.join(Ans))