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.
The input contains two integers $n$ and $k$, separated by a single space $(1 \le k < n \le 100)$.
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 |