Friendships [AtCoder Beginner Contest 131 E]

https://atcoder.jp/contests/abc131/tasks/abc131_e

解説

https://atcoder.jp/contests/abc131/submissions/6082165

こういう構築系は、最小ケースと最大ケースを考えるのが、常套テクである。
　
最小ケースは完全グラフを作ればK=0にできる。

最大ケースはスター型のような気がする。他に最大ケースが思いつかない。
スターのとき、中心の1つ以外の頂点でのペアが全て作れるので、(N-1)(N-2)/2が最大。
　
これもよくある方針だが、最小と最大の間はすべて何らかの方法で作ることができると仮定する。
どうやってこれを実現するかであるが、スター型でのペアの間に辺を貼っていけば1つずつ減らすことができそう。
で、実際これはできる。

int N, K;
vector<pair<int, int>> ans;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;

	rep(i, 1, N) ans.push_back({ 0, i });

	int k = (N - 1) * (N - 2) / 2;
	if (k < K) {
		cout << -1 << endl;
		return;
	}

	rep(i, 1, N) rep(j, i + 1, N) {
		if (K == k) break;

		ans.push_back({ i, j });
		k--;
	}

	int n = ans.size();
	printf("%d\n", n);
	fore(p, ans) printf("%d %d\n", p.first + 1, p.second + 1);
}