35278번 - 수열 정렬 수수께끼 스페셜 저지

SUAPC 왕국의 국왕은 커다란 상금을 걸고 아래의 수수께끼를 냈다.

• $1$부터 $N$까지의 수가 각각 하나씩 포함된 수열 $A$가 있다. $i$번째 수를 $A_i$라 했을 때, $A_i \neq i$이다. 이때 수열의 두 원소를 바꾸는 교환 연산을 $(N+1)/2$회 이하로 수행하여 수열을 오름차순으로 정렬하여라.

대부분의 사람은 위의 수수께끼를 풀 수 없다고 생각했지만, 자칭 수열 정렬 마스터인 어떤 사람이 나타나 이 수수께끼를 풀겠다고 선언했다. 국왕은 내일 모두가 보는 앞에서 이 수수께끼를 풀어보라고 지시했고, 수열 $A$에 $A_i = i$가 되는 순간 경보음이 울리는 경보 장치를 장착했다.

사실 수열 정렬 마스터도 이 수수께끼를 풀지 못한다. 그래서 그날 밤, 그는 수열 $A$에 몰래 접근해서 수열 $A$를 조작하기로 마음먹었다. 시간이 없으므로 교환 연산을 최대 $N/2$회 이하로 수행할 수 있으며, 중간에 $A_i = i$가 되는 경우가 없어야 한다. 그는 위의 조건대로 밤사이에 수열 $A$를 조작하여 다음날 수수께끼를 풀고 커다란 상금을 가져갈 수 있을까?

첫 번째 줄에 수열 $A$의 길이 $N$이 주어진다. ($3 \leq N \leq 200\,000$)

두 번째 줄에 서로 다른 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq N$; $A_i \neq i$)

만약 밤사이에 수열 $A$를 조작하고 수수께끼를 풀 수 있다면, 첫 번째 줄에 YES를 출력한다.

다음 줄에 밤사이에 수행한 연산의 횟수 $X$를 출력한다. ($0 \leq X \leq N/2$)

다음 $X$개의 줄에 걸쳐 두 원소를 바꾼 위치 $i$, $j$를 공백으로 구분하여 출력한다. 두 원소를 바꾼 뒤 $A_i = i$ 또는 $A_j = j$가 되는 경우는 없어야 한다. ($1 \leq i < j \leq N$)

다음 줄에 수수께끼를 푼 당일 수행한 연산의 횟수 $Y$를 출력한다. ($1 \leq Y \leq (N+1)/2$)

다음 $Y$개의 줄에 걸쳐 두 원소를 바꾼 위치 $i$, $j$를 공백으로 구분하여 출력한다. ($1 \leq i < j \leq N$)

가능한 정답이 여러 가지라면 그중 아무거나 출력한다.

만약 밤사이에 수열 $A$를 조작하고 수수께끼를 풀 수 없다면, 첫 번째 줄에 NO를 출력한다.