Binary Matrix Construction with Reachability Conditions

You are given two integers \(n\) and \(k\). Your task is to construct a binary matrix \(A\) of size \((n+1)\times(n+1)\) (indices from \(0\) to \(n\)) satisfying the following conditions:

• \(A_{i,i} = 1\) for all \(0 \le i \le n\).
• \(A_{i,i+1} = 1\) for all \(0 \le i \le n-1\).
• \(A_{i,j} = 0\) for all \(i > j\) (i.e. the matrix is upper-triangular).
• If \(A_{i,j} = 1\) with \(j-i > 1\), then there exists at least one \(t\) with \(i < t < j\) such that \(A_{i,t} = A_{t,j} = 1\).
• For every \(0 \le i \le j \le n\), the \((i,j)\) entry of \(A^k\) is strictly positive, i.e., \((A^k)_{i,j} > 0\).

You do not need to output the matrix. Instead, output all pairs \((i,j)\) with \(A_{i,j} = 1\) and \(j-i > 1\). Let \(m\) be the number of such pairs. Your solution will be scored based on the value of \(m\). If the output does not satisfy the conditions, you will receive no points for that test case.

Note: It can be shown that choosing \(A_{i,j} = 1\) for all \(i \le j\) yields a valid solution. In that case, conditions (1), (2), (3), and (4) are automatically satisfied, and condition (5) follows from the combinatorial properties of \(A^k\). Using this construction, the pairs to output are exactly those pairs \((i,j)\) such that \(0 \le i 1\).

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) (with \(n\ge 1\) and \(k\ge 1\)).

outputFormat

First, output an integer \(m\) representing the number of pairs \((i,j)\) such that \(A_{i,j} = 1\) and \(j-i > 1\). Then, output \(m\) lines, each containing two integers \(i\) and \(j\) (with \(0 \le i < j \le n\)) representing the indices of the matrix entry. Pairs can be output in any order, but typically the order is ascending by \(i\) then \(j\).

sample

3 1

3
0 2
0 3
1 3