Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Invariance of Tree

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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* = *p*_{1}*p*_{2}... *p*_{n}, 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 *p*_{u} and *p*_{v} 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* ≤ 10^{5}) — the size of the permutation (also equal to the size of the sought tree).

The second line contains permutation *p*_{i} (1 ≤ *p*_{i} ≤ *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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:32:56 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|