P8910 [RC-06] Operation Sequence

You are given $n$, and an array $[a_1,a_2,\dots,a_{n+1}]$ of length $n+1$. Initially, $a_i=i\ (1\le i\le n)$, and $a_{n+1}=0$. You may only perform the following type of operation, by printing a specific string: - Print `i j`: where $i,j$ are positive integers with $1\le i,j\le n+1$, meaning assign $a_i$ to $a_j$ (i.e., set $a_i=a_j$). Please cyclically shift the **first $n$ elements** of array $a$ to the **right** by $K$ positions. That is, after all operations you print are executed, it must satisfy: - For positions $i\ (1\le i\le K)$, $a_i = n-K+i$. - For positions $i\ (K+1\le i\le n)$, $a_i = i-K$. - The $(n+1)$-th element can be anything. You may perform at most $T=\lfloor1.5n\rfloor$ assignment operations. If you use more than $T$ operations, you can still get partial points. Specifically, let your number of operations be $S$: - If $S\le T$, you get $100$ points. - If $T4T$, you get $0$ points. Your score for this problem is the minimum score among all testdata in all test points.

This problem contains multiple groups of data in a single test point. The first line contains the number of data groups $T$. For each data group: The first line contains two positive integers $n,K$.

For each data group: Print the number of operations $k\ (0\le k\le 4T)$ on the first line. **Note that you do not need to minimize $k$.** Then print $k$ lines, each containing two positive integers $i,j$, representing one operation. $(1\le i,j\le n+1)$.

All data satisfy: $1\le T\le 10^4$, $1\le n\le 10^5$, $0\le K\le n-1$. It is guaranteed that, within the same test point, the sum of all $n$ does not exceed $5\times 10^5$. Translated by ChatGPT 5