A Permutation Problem

시간 제한3초메모리 제한512 MB

요약

1부터 n까지의 순열이 주어질 때, 모든 값 쌍을 정확히 한 번씩 교환해서 순열을 정렬하는 순서를 출력하거나, 불가능하면 불가능하다고 판별하는 문제이다.

난이도: 보통10점 중 7점
유형: 그리디, 구현, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

Zenyk has a permutation of n integers from 1 to n, inclusive. His task is to sort the permutation, and he has to swap each pair of integers exactly once.

Can you help him to do that?

입력

The first line contains a single integer n (2 ≤ n ≤ 1000). The second line contains the permutation P of integers between 1 and n.

출력

Print “no” if it’s impossible to sort the permutation. Otherwise, print n(n−1)/2 lines that describe the pairs of values (not indices) to swap on the corresponding turn.

예제3

예제 1
입력
```
4
3 2 4 1
```
예상 출력
```
1 2
4 1
1 3
2 3
2 4
3 4
```
예제 2
입력
```
3
1 3 2
```
예상 출력
```
1 3
3 2
1 2
```
예제 3
입력
```
2
1 2
```
예상 출력
```
no
```