Aizhan có dãy \(N\) số nguyên \(S[0],S[1],\ldots,S[N-1]\), gồm các số từ \(0\) đến \(N-1\), mỗi số xuất hiện đúng một lần. Cô muốn sắp xếp dãy tăng dần bằng cách đổi chỗ một số cặp phần tử. Bạn của cô là Ermek cũng sẽ đổi chỗ một số cặp phần tử, nhưng không nhất thiết giúp việc sắp xếp dễ hơn.

Hai người thay đổi dãy qua các vòng. Trong mỗi vòng, Ermek đổi chỗ trước, sau đó Aizhan thực hiện một phép đổi chỗ. Mỗi người chọn hai chỉ số hợp lệ rồi đổi chỗ các phần tử ở hai chỉ số đó. Hai chỉ số được phép bằng nhau; khi ấy một phần tử đổi chỗ với chính nó và dãy không thay đổi.

Aizhan biết Ermek không thực sự quan tâm đến việc sắp xếp \(S\) và biết chính xác những chỉ số mà Ermek sẽ chọn. Ermek dự định tham gia \(M\) vòng, đánh số từ \(0\) đến \(M-1\). Tại vòng \(i\), Ermek chọn hai chỉ số \(X[i]\) và \(Y[i]\).

Trước mỗi vòng, nếu thấy dãy đã tăng dần, Aizhan sẽ kết thúc toàn bộ quá trình. Cho dãy ban đầu và các chỉ số Ermek sẽ chọn, hãy tìm một dãy phép đổi chỗ mà Aizhan có thể dùng để sắp xếp \(S\). Trong một số subtask, dãy phép đổi chỗ phải ngắn nhất có thể. Đảm bảo có thể sắp xếp trong không quá \(M\) vòng.

Nếu dãy đã tăng dần ngay sau phép đổi chỗ của Ermek, Aizhan có thể đổi chỗ hai chỉ số bằng nhau, chẳng hạn \((0,0)\). Dãy vẫn tăng dần sau khi kết thúc vòng và Aizhan đạt mục tiêu. Nếu dãy ban đầu đã tăng dần, số vòng ít nhất là \(0\).

Ví dụ 1

Dãy ban đầu là \(S=(4,3,2,1,0)\) và Ermek sẵn sàng thực hiện \(M=6\) phép đổi chỗ. Hai dãy chỉ số là \(X=(0,1,2,3,0,1)\) và \(Y=(1,2,3,4,1,2)\); các cặp của Ermek lần lượt là \((0,1)\), \((1,2)\), \((2,3)\), \((3,4)\), \((0,1)\), \((1,2)\).

Aizhan có thể đưa dãy về \((0,1,2,3,4)\) trong ba vòng bằng cách chọn lần lượt \((0,4)\), \((1,3)\), \((3,4)\):

Ví dụ 2

Dãy ban đầu là \(S=(3,0,4,2,1)\) và Ermek sẵn sàng thực hiện \(M=5\) phép đổi chỗ. Các cặp chỉ số của Ermek lần lượt là \((1,1)\), \((4,0)\), \((2,3)\), \((1,4)\), \((0,4)\).

Aizhan có thể sắp xếp trong ba vòng, chẳng hạn chọn lần lượt \((1,4)\), \((4,2)\), \((2,2)\):

Chi tiết cài đặt

Cho \(S\), \(M\), \(X\), \(Y\), hãy tìm dãy phép đổi chỗ của Aizhan. Ở subtasks \(5\) và \(6\), phải tìm dãy ngắn nhất.

Trong C hoặc C++, cài đặt hàm trong header dùng chung sorting.h:

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]);

Trong Java, cài đặt phương thức sau trong lớp sorting:

public int findSwapPairs(int N, int[] S, int M, int[] X, int[] Y, int[] P, int[] Q)

Hàm được chương trình chấm gọi đúng một lần:

• N: độ dài dãy \(S\).
• S: mảng số nguyên chứa dãy ban đầu.
• M: số phép đổi chỗ Ermek dự định thực hiện.
• X, Y: hai mảng số nguyên dài \(M\). Tại vòng \(i\), với \(0 \le i \le M-1\), Ermek đổi chỗ các phần tử tại X[i], Y[i].
• P, Q: hai mảng số nguyên, mỗi mảng đã được cấp phát \(M\) phần tử, dùng để trả về một dãy phép đổi chỗ hợp lệ của Aizhan. Gọi \(R\) là độ dài dãy tìm được. Với \(0 \le i \le R-1\), ghi hai chỉ số Aizhan chọn ở vòng \(i\) vào P[i], Q[i].
• Hàm trả về \(R\), với \(0 \le R \le M\). Các chỉ số phải thuộc đoạn \([0,N-1]\); hai chỉ số của một phép đổi chỗ được phép bằng nhau.

Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "sorting.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp sorting, không viết phương thức main. Có thể trả về bất kỳ dãy phép đổi chỗ thỏa yêu cầu; bộ chấm kiểm tra tác dụng của các phép đổi chỗ, không so sánh nguyên văn với một đáp án mẫu.

Phân nhóm

Luôn tồn tại lời giải cần không quá \(M\) vòng. Mỗi subtask được trọn điểm nếu tất cả test của subtask đều đúng, nếu không được \(0\) điểm. Các mẫu là pretest \(0\) điểm.

Chương trình chấm mẫu

Chương trình chấm mẫu đọc tệp sorting.in:

• Dòng \(1\): N.
• Dòng \(2\): S[0] ... S[N-1].
• Dòng \(3\): M.
• Các dòng \(4,\ldots,M+3\): X[i] Y[i], theo thứ tự \(i=0,\ldots,M-1\).

Kết quả được in theo định dạng:

• Dòng \(1\): giá trị \(R\) trả về bởi findSwapPairs.
• Dòng \(2+i\), với \(0 \le i \le R-1\): P[i] Q[i].

Grader trên LQDOJ dùng đầu vào/đầu ra chuẩn thay cho tệp, giữ nguyên giao diện hàm.

Dữ liệu cho ví dụ 1:

5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2

Một kết quả hợp lệ:

3
0 4
1 3
3 4

Dữ liệu cho ví dụ 2:

5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4

Một kết quả hợp lệ:

3
1 4
4 2
2 2