题目描述

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

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

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

誘導部分グラフとは

グラフ $G$ の頂点部分集合 $X$ に対して，$X$ による $G$ の誘導部分グラフとは，「頂点集合が $X$ であり，辺集合が『 $G$ の辺であって $X$ 内の $2$ 頂点を結ぶもの全体』であるグラフ」を指します． 上記の条件では，頂点部分集合として空集合でも全体でもないもののみを考えていることに注意してください．

输入格式

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

$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$ を結んでいることを表す．
• 辺の順番（どの辺を何番目に出力するか）や頂点の順番（各辺についてどちらの端点を先に出力するか）は自由である．

题目大意

题目描述：

给出 $n$ 和 $d$，表示有一个 $n$ 个点 $nd$ 条边的图，我们设 $E$ 为构造图的点非空真集，加入点权之间相连的边，我们设 $D$ 为这个子图的 $\frac{\text{边的个数}}{\text{点的个数}}$。

点的个数边的个数，若存在一个图满足所有的 $D$ 都小于 $d$，就输出 Yes，并输出图，否则输出 No。

3 1

Yes
1 2
1 3
2 3

4 2

No

提示

制約

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

Sample Explanation 1

出力されたグラフの頂点集合は $\{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$ 未満であり，このグラフは条件を満たします．

Sample Explanation 2

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