ICPC Vietnam National Programming Contest 2020

Start

2020-11-14 16:00 AKST

ICPC Vietnam National Programming Contest 2020

End

2020-11-14 21:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -110 days 10:06:08

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
Cable Car

At $3\, 147.3$ meters high, Fansipan is the tallest mountain in the Indochina peninsula. To promote tourism, $n$ stations were built on the mountain, numbered from $1$ to $n$.

Two companies, Mobi and Vina are in charge of operating cable cars connecting the stations. Each of the two companies have $k$ cable cars. The $i$-th cable car of Mobi connects two stations $MS_ i$ and $ME_ i$. The $i$-th cable car of Vina connects two stations $VS_ i$ and $VE_ i$.

Two stations are called connected by a company, iff we can go from one station to the other by using cable cars only of that company. To achieve peaceful cooperation, the two companies agreed with the following conditions:

  • For every valid $i$, $MS_ i < ME_ i$ and $VS_ i < VE_ i$.

  • All $MS_ i$ are unique, all $ME_ i$ are unique.

  • All $VS_ i$ are unique, all $VE_ i$ are unique.

  • For any $i \ne j$, if $MS_ i < MS_ j$, then $ME_ i < ME_ j$.

  • For any $i \ne j$, if $VS_ i < VS_ j$, then $VE_ i < VE_ j$.

  • No pair of stations is connected by both companies. In other words, for every pair of stations $i$ and $j$, if $i$ and $j$ are connected by Mobi, they should not be connected by Vina, and vice versa.

Given $n$ and $k$, your task is to check whether it is possible for Mobi and Vina to each operates $k$ cable cars, satisfying all the above conditions.

Input

The input contains two integers $n$ and $k$, separated by a single space $(1 \le k < n \le 100)$.

Output

For each test case, if it is not possible to satisfy all the conditions, print ‘NO’. Otherwise, print ‘YES’, followed by $2 \cdot k$ lines. In the first $k$ lines, the $i$-th line contains two integers $MS_ i$ and $ME_ i$. In the last $k$ lines, the $i$-th line contains two integers $VS_ i$ and $VE_ i$.

Sample Input 1 Sample Output 1
3 1
YES
1 2
1 3
Sample Input 2 Sample Output 2
3 2
NO