CF1118E.Yet Another Ball Problem

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.

贝尔兰王国的国王正在举办一场舞会！共有 $n$ 对舞者受邀参加舞会，编号为 $1$ 至 $n$。每对舞者由一名男性和一名女性组成。每位舞者（无论男女）都身着单色服装，每套服装的颜色用一个介于 $1$ 到 $k$（含端点）之间的整数表示。

设第 $i$ 对中男性的服装颜色为 $b_i$，女性的服装颜色为 $g_i$。你需要为每位舞者的服装选定一种颜色（即确定值 $b_1, b_2, \dots, b_n$ 和 $g_1, g_2, \dots, g_n$），使得满足以下全部条件：

1. 对每个 $i$：$b_i$ 和 $g_i$ 均为介于 $1$ 到 $k$（含端点）之间的整数；
2. 不存在两对完全相同的舞者组合，即不存在两个下标 $i, j$（$i \ne j$），使得同时满足 $b_i = b_j$ 且 $g_i = g_j$；
3. 不存在某对舞者中男女服装颜色相同的情况，即对每个 $i$ 都有 $b_i \ne g_i$；
4. 对任意两个相邻（连续）的舞者对，其男性服装颜色互不相同，且女性服装颜色也互不相同；即对每个 $i = 1, 2, \dots, n-1$，均满足 $b_i \ne b_{i + 1}$ 且 $g_i \ne g_{i + 1}$。

我们来看一些颜色分配方案的正反示例（其中 $n=4$、$k=3$，每对中男性在前、女性在后）：

不合法的颜色分配方案（Bad color choosing）：

• $(1, 2)$, $(2, 3)$, $(3, 2)$, $(1, 2)$ — 违反第 2 条规则（存在完全相同的舞者对）；
• $(2, 3)$, $(1, 1)$, $(3, 2)$, $(1, 3)$ — 违反第 3 条规则（存在一对男女服装颜色相同）；
• $(1, 2)$, $(2, 3)$, $(1, 3)$, $(2, 1)$ — 违反第 4 条规则（存在两个相邻舞者对，其男性/女性服装颜色之一相同）。

合法的颜色分配方案（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)$。

你需要找出任意一种满足上述条件的颜色分配方案；若不存在这样的方案，则输出说明无解。

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.

输入仅有一行，包含两个整数 $n$ 和 $k$（$2 \le n, k \le 2 \cdot 10^5$），分别表示数对的个数和颜色的种数。

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.

如果无法找到任何合适的颜色选择方案，则输出 "NO"。

否则，先输出 "YES"，然后在接下来的 $n$ 行中输出各对伴侣的服装颜色。第 $i$ 行应包含两个整数 $b_i$ 和 $g_i$，分别表示第 $i$ 对中男性和女性的服装颜色。

每个字母可使用任意大小写（大写或小写）。例如，"YeS"、"no" 和 "yES" 均可接受。