Yet Another Ball Problem
Contest: Codeforces Round 540 (Div. 3)
Difficulty rating: 1700
Tags: constructive algorithms, implementation

The king of Berland organizes a ball! $$$n$$$ pair are invited to the ball, they are numbered from $$$1$$$ to $$$n$$$. Each pair consists of one man and one woman. Each dancer (either man or woman) has a monochrome costume. The color of each costume is represented by an integer from $$$1$$$ to $$$k$$$, inclusive.

Let $$$b_i$$$ be the color of the man's costume and $$$g_i$$$ be the color of the woman's costume in the $$$i$$$-th pair. You have to choose a color for each dancer's costume (i.e. values $$$b_1, b_2, \dots, b_n$$$ and $$$g_1, g_2, \dots g_n$$$) in such a way that:

1. for every $$$i$$$: $$$b_i$$$ and $$$g_i$$$ are integers between $$$1$$$ and $$$k$$$, inclusive;
2. there are no two completely identical pairs, i.e. no two indices $$$i, j$$$ ($$$i \ne j$$$) such that $$$b_i = b_j$$$ and $$$g_i = g_j$$$ at the same time;
3. there is no pair such that the color of the man's costume is the same as the color of the woman's costume in this pair, i.e. $$$b_i \ne g_i$$$ for every $$$i$$$;
4. for each two consecutive (adjacent) pairs both man's costume colors and woman's costume colors differ, i.e. for every $$$i$$$ from $$$1$$$ to $$$n-1$$$ the conditions $$$b_i \ne b_{i + 1}$$$ and $$$g_i \ne g_{i + 1}$$$ hold.

Let's take a look at the examples of bad and good color choosing (for $$$n=4$$$ and $$$k=3$$$, man is the first in a pair and woman is the second):

Bad color choosing:

- $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(1, 2)$$$ — contradiction with the second rule (there are equal pairs);
- $$$(2, 3)$$$, $$$(1, 1)$$$, $$$(3, 2)$$$, $$$(1, 3)$$$ — contradiction with the third rule (there is a pair with costumes of the same color);
- $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 1)$$$ — contradiction with the fourth rule (there are two consecutive pairs such that colors of costumes of men/women are the same).

Good color choosing:

- $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(1, 3)$$$, $$$(3, 1)$$$;
- $$$(1, 2)$$$, $$$(3, 1)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$;
- $$$(3, 1)$$$, $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$.

You have to find any suitable color choosing or say that no suitable choosing exists.

Input format:
The only line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n, k \le 2 \cdot 10^5$$$) — the number of pairs and the number of colors.

Output format:
If it is impossible to find any suitable colors choosing, print "NO".

Otherwise print "YES" and then the colors of the costumes of pairs in the next $$$n$$$ lines. The $$$i$$$-th line should contain two integers $$$b_i$$$ and $$$g_i$$$ — colors of costumes of man and woman in the $$$i$$$-th pair, respectively.

You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
4 3

Example output:
YES
3 1
1 3
3 2
2 3

Example input:
10 4

Example output:
YES
2 1
1 3
4 2
3 4
4 3
3 2
2 4
4 1
1 4
3 1

Editorial:
The first observation: we cannot construct more than $$$k(k-1)$$$ pairs at all due to second and third rules.
The second observation: we always can construct an answer which will contain all $$$k(k-1)$$$ pairs (and get some prefix of this answer if we need less than $$$k(k-1)$$$ pairs). Ho do we do that?
Let man's costumes colors be in the following order: $$$1, 2, \dots, k; 1, 2, \dots, k; 1, 2, \dots, k$$$ and so on. Now we have to set some colors to woman's costumes. The first thing comes to mind is to use some cyclic shift of $$$1, 2, \dots, k$$$. And it is the best thing we can do! So let women's costumes colors be in the following order: $$$2, 3, \dots, k, 1; 3, 4, \dots, k, 1, 2; 4, 5, \dots, k, 1, 2, 3$$$ ans so on. So we use each cyclic shift of $$$1, 2, \dots, k$$$ in order from second to last. The maximum number of pairs can be obtained when $$$k=447$$$ and the number of such pairs is $$$n=199362$$$.
So now we have to prove that second, third and fourth rules are satisfied (or write a stress test, it is not so hard to do it). The easiest way to prove all rules are satisfied is the following: if some element $$$x$$$ in the left part has position $$$i$$$ (let's consider all positions modulo $$$k$$$) then each element $$$x$$$ in the right part will have all positions expect $$$i$$$ in order $$$i-1, i-2, \dots, i-k+1$$$ (you can see it from our placement). Now we can see that all rules are satisfied because of such a placement.