1118E.md (2896B)
1 Source: https://codeforces.com/problemset/problem/1118/E 2 3 E. Yet Another Ball Problem 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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: 24 25 1. for every $i$: $b_i$ and $g_i$ are integers between $1$ and $k$, inclusive; 26 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; 27 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$; 28 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. 29 30 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): 31 32 Bad color choosing: 33 34 * $(1, 2)$, $(2, 3)$, $(3, 2)$, $(1, 2)$ — contradiction with the second rule (there are equal pairs); 35 * $(2, 3)$, $(1, 1)$, $(3, 2)$, $(1, 3)$ — contradiction with the third rule (there is a pair with costumes of the same color); 36 * $(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). 37 38 Good color choosing: 39 40 * $(1, 2)$, $(2, 1)$, $(1, 3)$, $(3, 1)$; 41 * $(1, 2)$, $(3, 1)$, $(2, 3)$, $(3, 2)$; 42 * $(3, 1)$, $(1, 2)$, $(2, 3)$, $(3, 2)$. 43 44 You have to find any suitable color choosing or say that no suitable choosing exists. 45 46 Input 47 48 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. 49 50 Output 51 52 If it is impossible to find any suitable colors choosing, print "NO". 53 54 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. 55 56 You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable. 57 58 Examples 59 60 Input 61 62 ``` 63 4 3 64 ``` 65 66 Output 67 68 ``` 69 YES 70 3 1 71 1 3 72 3 2 73 2 3 74 ``` 75 76 Input 77 78 ``` 79 10 4 80 ``` 81 82 Output 83 84 ``` 85 YES 86 2 1 87 1 3 88 4 2 89 3 4 90 4 3 91 3 2 92 2 4 93 4 1 94 1 4 95 3 1 96 ``` 97 98 Input 99 100 ``` 101 13 4 102 ``` 103 104 Output 105 106 ``` 107 NO 108 ```