CF1118E Yet Another Ball Problem

Berland 国王举办了一场舞会！共有 $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 \ne j$ 使得 $b_i = b_j$ 且 $g_i = g_j$ 同时成立； 3. 不存在某一对嘉宾中男士和女士的服装颜色相同，即对于每个 $i$，$b_i \ne g_i$； 4. 对于任意相邻的两对嘉宾，男士的服装颜色和女士的服装颜色都不相同，即对于每个 $i$（$1 \le i \le n-1$），都有 $b_i \ne b_{i+1}$ 且 $g_i \ne g_{i+1}$。 下面是一些不合法和合法的配色示例（以 $n=4$，$k=3$ 为例，括号中第一个数字为男士颜色，第二个为女士颜色）： 不合法的配色： - $(1, 2)$，$(2, 3)$，$(3, 2)$，$(1, 2)$ —— 违反第二条规则（存在相同的两对）； - $(2, 3)$，$(1, 1)$，$(3, 2)$，$(1, 3)$ —— 违反第三条规则（存在一对男女服装颜色相同）； - $(1, 2)$，$(2, 3)$，$(1, 3)$，$(2, 1)$ —— 违反第四条规则（存在相邻两对男士或女士服装颜色相同）。 合法的配色： - $(1, 2)$，$(2, 1)$，$(1, 3)$，$(3, 1)$； - $(1, 2)$，$(3, 1)$，$(2, 3)$，$(3, 2)$； - $(3, 1)$，$(1, 2)$，$(2, 3)$，$(3, 2)$。 你需要给出任意一种满足条件的配色方案，或者说明不存在这样的方案。

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

如果不存在满足条件的配色方案，输出 "NO"。 否则，先输出 "YES"，然后在接下来的 $n$ 行中，每行输出两个整数 $b_i$ 和 $g_i$，分别表示第 $i$ 对中男士和女士的服装颜色。 你可以以任意大小写输出字母。例如，"YeS"、"no" 和 "yES" 都是可以接受的。

由 ChatGPT 4.1 翻译