Bine-i șade mesei mele

"How fine my table looks, with all my kin around it!" — Bine-i șade mesei mele

You are the host of a grand feast. There are $n$ kin gathered at your table. When two kin chat, they form a link. A kin is considered special if they chat with every single person at the feast.

You want the party to be lively, but you hate exclusive groups. A club is a group of kin where everyone chats with everyone else. To keep the peace, you strictly forbid any club of size $k+1$ (also known as a clique).

However, the kin are as social as possible: the links are so dense that if you force any two kin who are not currently chatting to start a chat, a club of size $k+1$ will instantly form!

Task

To keep things humble, you want to find a seating and chatting plan that follows these rules while keeping the number of special kin to an absolute minimum.

In short, given $n$ and $k$, construct an undirected graph with $n$ nodes (the kin) and $m$ edges (the chats) such that:

1. The graph does not contain any $(k+1)$-cliques.
2. Adding any new edge between two unconnected nodes creates at least one $(k+1)$-clique.
3. The number of special nodes (nodes with degree $n-1$) is minimized.

Input data

The first and only line of the input contains two integers, $n$ and $k$.

Output data

The first line of the output must contain $m$, the number of edges in your graph.

The next $m$ lines must contain two integers $u$ and $v$, representing a link between kin $u$ and kin $v$.

The nodes are numbered from $1$ to $n$. You can print the edges in any order. If there are multiple valid graphs, you can print any of them.

Constraints and clarifications

• $3 \le n \le 1\ 000$
• $n / 2 < k \le n$

Example

stdin

3 3

stdout

3
1 2
1 3
2 3