22096번 - СНМ 스페셜 저지다국어

Как Вы уже могли заметить, в жюри Russian Code Cup любят обратные задачи. Вот еще одна!

Система непересекающихся множеств — это структура данных, которая позволят хранить набор элементов, представленных в виде набора непересекающихся множеств. Она позволяет выполнять две операции:

• union(a, b) — объединяет два множества, содержащие элементы a и b.
• find(a) — возвращает некоторого представителя множества, в котором содержится a. find(a) = find(b) тогда и только тогда, когда a и b содержатся в одном множестве.

Популярным подходом к реализации данной структуры данных является реализация в виде леса корневых деревьев. Каждое множество представляется в виде корневого дерева, представителем которого является корень дерева. Родителя вершины i обозначим parent[i] (для корня дерева положим parent[i] = i). Изначально, каждый элемент находится в своем множестве и parent[i] = i для всех i. Операция union в таком представлении реализуется, как подвешивание одного из корней дерева к другому. Операция find реализуется, как простой проход по ссылкам к родителю, пока не достигнут корень дерева. Для простоты будем считать, что аргументы процедуры union — корни различных деревьев.

Также в этой задаче используется ранговая эвристика: введем дополнительную величину rank[i], которая изначально равна нулю для всех i. Операция union(a, b) работает следующим образом: если rank[a] = rank[b], то rank[a] увеличивается на единицу. После этого вершина с меньшим rank подвешивается к вершине с большим rank.

Приведем псевдокод процедур union и find.

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

Вам дан массив parent[i]. Существует ли такая последовательность операций union , что после ее выполнения массив parent станет равен заданному?

Первая строка содержит целое число n (1 ≤ n ≤ 10⁴). Вторая строка содержит n целых чисел parent[1], ..., parent[n] (1 ≤ parent[i] ≤ n для всех i от 1 до n).

Если требуемой последовательности не существует, выведите -1. Иначе в первой строке выведите целое число k ≥ 0 — количество операций. Затем выведите k пар чисел a_i b_i (1 ≤ a_i, b_i ≤ n) — аргументы i-й операции union. К моменту выполнения i-й операции a_i и b_i должны быть корнями различных деревьев.