서로소 집합

이미 눈치챘을 수도 있지만, Russian Code Cup 심사위원들은 역방향 문제를 좋아한다. 이번에도 그런 문제다!

서로소 집합은 원소들을 서로 겹치지 않는 여러 집합으로 나눠 저장하는 자료 구조다. 이 구조는 두 가지 연산을 지원한다.

• union(a, b) — 원소 a와 b가 각각 속한 두 집합을 합친다.
• find(a) — a가 속한 집합의 대표 원소 하나를 반환한다. a와 b가 같은 집합에 속해 있을 때, 그리고 그때만 find(a) = find(b)이다.

이 자료 구조를 구현하는 흔한 방법은 루트 있는 트리들의 숲으로 표현하는 것이다. 각 집합은 하나의 루트 있는 트리로 표현하고, 트리의 루트가 그 집합의 대표가 된다. 정점 i의 부모를 parent[i]라 하자(트리의 루트에 대해서는 parent[i] = i로 둔다). 처음에는 각 원소가 자기 자신만을 원소로 갖는 집합에 속해 있고, 모든 i에 대해 parent[i] = i이다. 이런 표현에서 union 연산은 한 트리의 루트를 다른 트리의 루트에 매다는 것으로 구현된다. find 연산은 트리의 루트에 도달할 때까지 부모 링크를 따라가는 것으로 구현된다. 편의상 union 프로시저의 인자는 서로 다른 트리의 루트라고 하자.

이 문제에서는 랭크 휴리스틱도 사용한다. rank[i]라는 값을 추가로 두고, 모든 i에 대해 처음에는 0으로 둔다. union(a, b) 연산은 다음과 같이 동작한다. rank[a] = rank[b]이면 rank[a]를 1 늘린다. 그다음 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 연산의 순서가 존재하는가?

첫째 줄에 정수 n이 주어진다(1 ≤ n ≤ 104). 둘째 줄에 n개의 정수 parent[1], ..., parent[n]이 주어진다(1 ≤ parent[i] ≤ n, 1 ≤ i ≤ n인 모든 i).

조건을 만족하는 순서가 존재하지 않으면 -1을 출력한다. 그렇지 않으면 첫째 줄에 연산의 개수 k ≥ 0을 출력한다. 그다음 k개의 줄에 걸쳐 i번째 union 연산의 인자 ai bi를 출력한다(1 ≤ ai, bi ≤ n). i번째 연산을 수행하는 시점에 ai와 bi는 서로 다른 트리의 루트여야 한다.