Problem Description

Given $n, k$, you need to construct a matrix $A_{i,j}$ that only contains $0$ and $1$, where $0\le i,j\le n$, satisfying:

1. $A_{i,i}=1$.
2. $A_{i,i+1}=1$.
3. For $i>j$, $A_{i,j}=0$.
4. If $A_{i,j}=1$ and $j-i>1$, then there exists $i<t<j$ such that $A_{i,t}=A_{t,j}=1$.
5. For $i\le j$, $(A^k)_{i,j}>0$.

You need to output every $(i,j)$ such that $A_{i,j}=1$ and $j-i>1$. Let there be $m$ such pairs $(i,j)$.

If your output does not meet the requirements, you cannot get any score for that test point. If your output meets the requirements, then it will be scored based on $m$.

Input Format

One line with two integers $n, k$.

Output Format

The first line contains an integer $m$. The next $m$ lines each contain two integers $i, j$, representing each pair $(i,j)$ that satisfies $A_{i,j}=1$ and $j-i>1$, in order.

3 2

1
0 2

Hint

For $100\%$ of the testdata, $1900\le n\le 2000$ and $2\le k\le 15$.

Each $2\le k\le 15$ corresponds to a subtask with total score $s(k)$. The score of each subtask is the minimum score among all test points in that subtask.

For each test point, the score equals the subtask's total score multiplied by $\max\left(0,1-\sqrt{\max\left(0,\frac{m}{n\cdot f(k)}-1\right)}\right)$.

Translated by ChatGPT 5