차원문

차원문은 매우 편리한 교통수단이다. 차원문은 평범한 문처럼 생겼지만, 문을 열고 들어가면 다른 공간으로 이동할 수 있는 특별한 성질이 있다. 단, 반대 방향으로 차원문을 이용할 수는 없다.

ANA 나라에는 $N$개의 도시가 있다. 각 도시는 $1, 2, \cdots, N$번으로 번호가 매겨져 있다. 차원문을 다루는 차원술사 인수는 $1, 2, \cdots, N$번 도시로 이동할 수 있는 차원문을 만들고, 각 차원문에 $1, 2, \cdots, N$번으로 번호를 매겼다. 그리고 이를 $N$개의 도시에 하나씩 무작위로 설치했다. $i$번 도시에 설치한 차원문의 번호는 $a_i$번이며, 이 차원문은 $a_i$번 도시로 향한다.

그런데 인수는 임의의 한 도시에서 차원문만을 이용해서 다른 모든 도시를 방문하는 것이 불가능할 수도 있다는 것을 알게 되었다. 그래서 인수는 서로 다른 두 도시를 골라 두 도시의 차원문을 서로 바꾸는 마법을 몇 번 사용해서 이 문제를 해결하려고 한다. 마법을 쓰려면 마나가 필요한데, 두 차원문 번호 차의 제곱만큼 마나가 든다. 예를 들어 1번 도시에 설치된 차원문이 4번 도시로 향하는 4번 차원문이고, 4번 도시의 차원문이 6번 도시로 향하는 6번 차원문이라면, 두 차원문을 바꾸는 데 $(4-6)^2=4$만큼의 마나가 필요하다.

임의의 한 도시에서 차원문만을 이용해서 다른 모든 도시를 방문할 수 있도록 만드는 데 필요한 최소 마나를 구하라. 그리고 마법을 어떻게 사용해야 하는지도 구하라. 단, 마법을 사용하는 횟수가 최소일 필요는 없다.

첫째 줄에 정수 $N$($2 \le N \le 200\,000$)이 주어진다.

둘째 줄에 정수 $a_1, a_2, \cdots, a_N$($1 \le a_i \le N$)이 공백으로 구분되어 주어진다.

첫째 줄에 필요한 최소 마나 $C$와 마법을 사용하는 횟수 $M$을 공백으로 구분하여 출력한다. 마법을 사용하는 횟수가 최소일 필요는 없다.

둘째 줄부터 $M$개의 줄에 걸쳐, 차원문을 바꿔야 하는 두 도시의 번호를 공백으로 구분하여 순서대로 출력한다.