Задача . E. Очередная задача про бал

Король Берляндии устраивает бал! На него приглашены \(n\) пар, они пронумерованы от \(1\) до \(n\). Каждая пара состоит из одного мужчины и одной женщины. Каждый танцор (то есть и мужчина, и женщина) должен надеть одноцветный костюм. Цвет каждого костюма можно обозначить целым числом от \(1\) до \(k\) включительно.

Пусть \(b_i\) — цвет костюма мужчины, а \(g_i\) — цвет костюма женщины в \(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. не существует такой пары, что цвет костюма мужчины равен цвету костюма женщины в этой паре, то есть \(b_i \ne g_i\) для всех \(i\);
4. для каждых двух последовательных (соседних) пар цвета костюмов мужчин и цвета костюмов женщин отличаются, то есть для всех \(i\) от \(1\) до \(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)\).

Вам необходимо найти любой подходящий выбор цветов или сказать, что таких выборов не существует.