配点 : $500$ 点

問題文

頂点集合が空でない単純無向グラフの密度を $\displaystyle\frac{(辺数)}{(頂点数)}$ と定義します．

正整数 $N, D$ が与えられます． $N$ 頂点 $DN$ 辺の単純無向グラフ $G$ であって，以下の条件を満たすものが存在するかどうかを判定し，存在するならそのようなグラフを $1$ つ求めてください．

条件: $G$ の頂点集合を $V$ とする． $V$ の任意の空でない真部分集合 $X$ に対して，$X$ による $G$ の誘導部分グラフの密度は $D$ 未満である．

制約

• $N \geq 1$
• $D \geq 1$
• $DN \leq 5 \times 10^4$

入力

入力は以下の形式で標準入力から与えられる．

$N$ $D$

出力

条件を満たす単純無向グラフが存在するなら Yes を，存在しないなら No を出力せよ． さらに，Yes の場合には，続く $DN$ 行に条件を満たすグラフを以下の形式で出力せよ． 条件を満たすグラフが複数存在する場合，そのようなグラフのうちどれを出力しても正答と見なされる．

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{DN}$ $B_{DN}$

• $1 \leq A_i, B_i \leq N \ \ (1 \leq i \leq DN)$
• $A_i \neq B_i \ \ (1 \leq i \leq DN)$
• $\{A_i, B_i\} \neq \{A_j, B_j\} \ \ (1 \leq i < j \leq DN)$
• グラフの頂点には $1$ から $N$ までの番号が付いているものとする．
• $i$ 行目の出力は，$i$ 番目の辺が頂点 $A_i$ と頂点 $B_i$ を結んでいることを表す．
• 辺の順番（どの辺を何番目に出力するか）や頂点の順番（各辺についてどちらの端点を先に出力するか）は自由である．

3 1

Yes
1 2
1 3
2 3

出力されたグラフの頂点集合は $\{1, 2, 3\}$，辺集合は $\{(1, 2), (1, 3), (2, 3)\}$ であり，単純です． 頂点集合の空でない真部分集合 $X$ としては $\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}$ の $6$ 通りが考えられ，

• $X = \{1\}, \{2\}, \{3\}$ のとき，$X$ による誘導部分グラフの辺集合は空集合であり，その密度は $\displaystyle\frac{0}{1} = 0$，
• $X = \{1, 2\}, \{1, 3\}, \{2, 3\}$ のとき，$X$ による誘導部分グラフの辺集合はそれぞれ $\{(1, 2)\}, \{(1, 3)\}, \{(2, 3)\}$ であり，いずれも密度は $\displaystyle\frac{1}{2}$ です．

全ての場合に対して誘導部分グラフの密度は $D = 1$ 未満であり，このグラフは条件を満たします．

4 2

No

$4$ 頂点 $8$ 辺の単純無向グラフは存在しません．