Disjoint Set Union

As you may have noticed, the jury of the Russian Code Cup likes reverse problems. Here is another one!

A disjoint set union is a data structure that stores a collection of elements split into disjoint sets. It supports two operations:

• union(a, b) merges the two sets containing elements a and b.
• find(a) returns some representative of the set containing a. find(a) = find(b) if and only if a and b belong to the same set.

A common way to implement this data structure is as a forest of rooted trees. Each set is represented by a rooted tree, and the root of the tree is its representative. Let parent[i] denote the parent of vertex i (for the root of a tree, set parent[i] = i). Initially each element is in its own set and parent[i] = i for all i. In this representation, a union operation attaches the root of one tree to the root of another. A find operation walks up the parent links until it reaches the root of the tree. For simplicity, assume that the arguments of the union procedure are roots of distinct trees.

This problem also uses the rank heuristic. Introduce an extra value rank[i], initially zero for all i. The operation union(a, b) works as follows. If rank[a] = rank[b], then rank[a] increases by one. After that, the vertex with the smaller rank is attached to the vertex with the larger rank.

Here is the pseudocode of the union and find procedures.

union(a, b)
  if rank[a] == rank[b] then
    rank[a] = rank[a] + 1
  if rank[a] > rank[b] then
    parent[b] = a
  else
    parent[a] = b

find(a)
  while parent[a] != a do
    a = parent[a]
  return a

You are given an array parent[i]. Does there exist a sequence of union operations such that after performing it the array parent becomes equal to the given one?

The first line contains an integer n (1 ≤ n ≤ 104). The second line contains n integers parent[1], ..., parent[n] (1 ≤ parent[i] ≤ n for all i from 1 to n).

If the required sequence does not exist, output -1. Otherwise, on the first line output an integer k ≥ 0, the number of operations. Then output k pairs of integers ai bi (1 ≤ ai, bi ≤ n), the arguments of the i-th union operation. At the moment the i-th operation is performed, ai and bi must be roots of distinct trees.