Valera và phép hoán đổi

Cho một hoán vị $p$ độ dài $n$, tức là dãy gồm $n$ số nguyên phân biệt $p_1,p_2,\dots ,p_n$ với $1\le p_i\le n$. Hoán vị được gọi là đồng nhất nếu $p_i=i$ với mọi $i$.

Một phép hoán đổi $(i,j)$ là thao tác đổi chỗ hai phần tử $p_i$ và $p_j$. Đặt $f(p)$ là số phép hoán đổi tối thiểu cần thực hiện để biến hoán vị $p$ thành hoán vị đồng nhất.

Cho hoán vị $p$ và số nguyên $m$. Hãy tìm cách biến $p$ thành một hoán vị $q$ nào đó sao cho $f(q)=m$, sử dụng số phép hoán đổi ít nhất có thể. Nếu có nhiều dãy hoán đổi có cùng độ dài nhỏ nhất, hãy in ra dãy có thứ tự từ điển nhỏ nhất (so sánh dãy số nguyên $x_1,x_2,\dots ,x_{2k}$ mà bạn in ra).

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $n$ — độ dài của hoán vị $p$.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $p_1,p_2,\dots ,p_n$ — hoán vị ban đầu.
• Dòng thứ ba chứa số nguyên $m$.

Dữ liệu ra

• Dòng thứ nhất in số nguyên $k$ — số phép hoán đổi nhỏ nhất.
• Dòng thứ hai in $2k$ số nguyên $x_1,x_2,\dots ,x_{2k}$, mô tả dãy hoán đổi: bạn lần lượt thực hiện các phép hoán đổi $(x_1,x_2),(x_3,x_4),\dots ,(x_{2k-1},x_{2k})$. Nếu có nhiều dãy thoả mãn, in dãy có thứ tự từ điển nhỏ nhất.

Ràng buộc

• $1\le n\le 3000$
• $1\le p_i\le n$ và các $p_i$ phân biệt
• $0\le m<n$

Ví dụ