/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
頂点集合が空でない単純無向グラフの密度を \displaystyle\frac{(辺数)}{(頂点数)} と定義します．
正整数 N, D が与えられます． N 頂点 DN 辺の単純無向グラフ G であって，以下の条件を満たすものが存在するかどうかを判定し，存在するならそのようなグラフを 1 つ求めてください．
条件: G の頂点集合を V とする． V の任意の空でない真部分集合 X に対して，X による G の誘導部分グラフの密度は D 未満である．
誘導部分グラフとは
グラフ G の頂点部分集合 X に対して，X による G の誘導部分グラフとは，「頂点集合が X であり，辺集合が『 G の辺であって X 内の 2 頂点を結ぶもの全体』であるグラフ」を指します． 上記の条件では，頂点部分集合として空集合でも全体でもないもののみを考えていることに注意してください．
制約
- 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 を結んでいることを表す．
- 辺の順番（どの辺を何番目に出力するか）や頂点の順番（各辺についてどちらの端点を先に出力するか）は自由である．
入力例 1
3 1
出力例 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 未満であり，このグラフは条件を満たします．
入力例 2
4 2
出力例 2
No
4 頂点 8 辺の単純無向グラフは存在しません．
Score : 500 points
Problem Statement
We define the density of a non-empty simple undirected graph as \displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}.
You are given positive integers N and D. Determine whether there is a simple undirected graph G with N vertices and DN edges that satisfies the following condition. If it exists, find one such graph.
Condition: Let V be the vertex set of G. For any non-empty proper subset X of V, the density of the induced subgraph of G by X is strictly less than D.
What is an induced subgraph?
For a vertex subset X of graph G, the induced subgraph of G by X is the graph with vertex set X and edge set containing all edges of G that connect two vertices in X. In the above condition, note that we only consider vertex subsets that are neither empty nor the entire set.
Constraints
- N \geq 1
- D \geq 1
- DN \leq 5 \times 10^4
Input
The input is given from Standard Input in the following format:
N D
Output
If there is a simple undirected graph that satisfies the condition, print Yes; otherwise, print No.
Furthermore, in the case of Yes, print a graph that satisfies the condition in the following format in the next DN lines.
If multiple graphs satisfy the condition, any of them will be considered correct.
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)
- The vertices of the graph are numbered from 1 to N.
- The i-th line of the output represents that the i-th edge connects vertex A_i and vertex B_i.
- The order of the edges (which edge is printed first) and the order of the vertices (which endpoint of each edge is printed first) may be arbitrary.
Sample Input 1
3 1
Sample Output 1
Yes 1 2 1 3 2 3
The printed graph has vertex set \{1, 2, 3\} and edge set \{(1, 2), (1, 3), (2, 3)\}, and is simple. The vertex set X has 6 non-empty proper subsets: \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}.
- For X = \{1\}, \{2\}, \{3\}, the edge sets of the induced subgraphs by X are empty, and the densities are \displaystyle\frac{0}{1} = 0.
- For X = \{1, 2\}, \{1, 3\}, \{2, 3\}, the edge sets of the induced subgraphs by X are \{(1, 2)\}, \{(1, 3)\}, \{(2, 3)\}, respectively, and the densities are all \displaystyle\frac{1}{2}.
In all cases, the density of the induced subgraph is strictly less than D = 1, so this graph satisfies the condition.
Sample Input 2
4 2
Sample Output 2
No
A simple undirected graph with 4 vertices and 8 edges does not exist.