Graph Game

Time limit1sMemory limit1024 MB

Summary

Given N vertices, add K edges one at a time without repeating an edge or creating an odd cycle, or report that it is impossible.

Level: Medium4 of 10
Topics: Graph, Math, Implementation
Solved: No attempts yet

Problem

Chunbae is playing a graph game. The game starts with a graph that has $N$ vertices and no edges. Players add undirected edges one at a time. Vertices are numbered from 1 to $N$ .

Each edge added must satisfy the following conditions.

If the graph already has an edge connecting vertices $u$ and $v$ , another edge connecting $u$ and $v$ cannot be added.
If, after adding an edge connecting $u$ and $v$ , the graph has at least one cycle with an odd number of edges, that edge cannot be added.

If Chunbae can add $K$ edges to the graph while satisfying these conditions, Chunbae wins. Otherwise, Chunbae loses.

Determine whether Chunbae can win. If so, find the $K$ edges Chunbae must add.

Input

The first line contains $N$ and $K$ separated by a space. ( $1 \le N \le 100\,000$ , $1 \le K \le 300\,000$ )

Output

On the first line, print YES if Chunbae can win, or NO otherwise.

If Chunbae can win, print the $K$ edges Chunbae must add, one per line in the order they are added. Each line contains the two vertices that the edge connects.

Examples2

Example 1
Input
```
3 2
```
Expected output
```
YES
1 2
3 2
```
Example 2
Input
```
3 3
```
Expected output
```
NO
```