AT_arc161_d [ARC161D] Everywhere is Sparser than Whole (Construction)

[problemUrl]: https://atcoder.jp/contests/arc161/tasks/arc161_d 頂点集合が空でない単純無向グラフの**密度**を $ \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\

### 制約 - $ 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 $ 辺の単純無向グラフは存在しません．