King's Puzzle

Time limit3sMemory limit1024 MB

Summary

Build a connected simple graph on n vertices whose degrees take exactly k distinct values, or report NO if that is impossible.

Level: Medium6 of 10
Topics: Greedy, Implementation, Math
Solved: No attempts yet

Problem

King Kendrick is the sovereign ruler of the Kotlin Kingdom, which has $n$ cities. He is preparing for the next government session, and the cities must be connected by bidirectional roads. Four ministries have set requirements:

Ministry of Transport and Digital Infrastructure: All cities must be connected, so there is a path between any two cities.
Ministry of Environment: No loop road is allowed, so no road may connect a city to itself.
Treasury Department: There may be at most one road between any pair of cities.
Ministry of ICPC: If $a_i$ is the number of roads connected to city $i$ , then the set $\{a_1, \ldots, a_n\}$ must consist of exactly $k$ distinct numbers.

King Kendrick has trouble with the ICPC Ministry's requirement and asks for help. Find any set of roads that meets all four requirements, or report that it is impossible.

Input

The only line contains two integers $n$ and $k$ ( $1 \le k \le n \le 500$ ).

Output

If it is impossible to meet all requirements, print NO on a single line.

Otherwise, print YES on the first line. On the second line, print the number of roads $m$ ( $0 \le m \le \frac{n \cdot (n - 1)}{2}$ ). Then print $m$ lines, each with two integers $a$ and $b$ ( $1 \le a, b \le n$ ), the two cities connected by a road.

Examples2

Example 1
Input
```
5 2
```
Expected output
```
YES
4
1 2
1 3
1 4
1 5
```
Example 2
Input
```
4 1
```
Expected output
```
YES
4
1 2
2 3
3 4
4 1
```