Submission #69914352

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

using mint = atcoder::modint998244353;

void solve() {
	int n;
	cin >> n;
	if (n < 6) {
		cout << "-1\n";
		return;
	}
	if (n == 8) {
		vector<pair<int, int>> ans;
		ans.push_back({1, 2});
		ans.push_back({1, 4});
		ans.push_back({1, 6});
		ans.push_back({2, 3});
		ans.push_back({2, 5});
		ans.push_back({3, 4});
		ans.push_back({3, 8});
		ans.push_back({4, 7});
		ans.push_back({5, 6});
		ans.push_back({5, 8});
		ans.push_back({6, 7});
		ans.push_back({7, 8});
		cout << ans.size() << '\n';
		for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
		return;
	}
	if (n == 9) {
		vector<pair<int, int>> ans;
		ans.push_back({1, 2});
		ans.push_back({1, 4});
		ans.push_back({1, 6});
		ans.push_back({2, 3});
		ans.push_back({2, 5});
		ans.push_back({3, 4});
		ans.push_back({3, 8});
		ans.push_back({4, 7});
		ans.push_back({5, 6});
		ans.push_back({5, 8});
		ans.push_back({6, 7});
		ans.push_back({7, 8});

		ans.push_back({1, 9});
		ans.push_back({3, 9});
		ans.push_back({5, 9});
		ans.push_back({7, 9});
		cout << ans.size() << '\n';
		for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
		return;
	}
	vector<pair<int, int>> ans;
	vector<int> v(n);
	if (n % 4 == 3) {
		n--;
		int m = (n - 2) / 2;
		rep(i, 0, n) {
			for (int j = 1; j < m; j += 2) {
				ans.push_back({i, (i + j) % n});
			}
		}
		rep(i, 0, n) {
			if (i & 1) ans.push_back({i, n});
		}
		rep(i, 0, n / 2) v[i] = i + 1;
		rep(i, n / 2, n) v[i] = n + n / 2 - i;
		v[n] = n + 1;
	} else if (n % 4 == 1) {
		n--;
		int n1 = n - 6, n2 = 6;
		{
			int m = (n1 - 2) / 2;
			rep(i, 0, n1) {
				for (int j = 1; j < m; j += 2) {
					ans.push_back({i, (i + j) % n1});
				}
			}
			rep(i, 0, n1 / 2) v[i] = i + 1;
			rep(i, n1 / 2, n1) v[i] = n + n1 / 2 - i;
		}
		{
			int m = (n2 - 2) / 2;
			rep(i, 0, n2) {
				for (int j = 1; j < m; j += 2) {
					ans.push_back({n1 + i, n1 + (i + j) % n2});
				}
			}
			rep(i, 0, n2 / 2) v[n1 + i] = i + 1 + n1 / 2;
			rep(i, n2 / 2, n2) v[n1 + i] = n - n1 / 2 + n2 / 2 - i;
		}
		rep(i, 0, n1) {
			int t = i & 1;
			rep(j, 0, 3) {
				ans.push_back({i, n1 + j * 2 + t});
			}
		}
		rep(i, 0, n) {
			if (i & 1) ans.push_back({i, n});
		}
		v[n] = n + 1;
	} else if (n % 4 == 2) {
		int m = (n - 2) / 2;
		rep(i, 0, n) {
			for (int j = 1; j < m; j += 2) {
				ans.push_back({i, (i + j) % n});
			}
		}
		rep(i, 0, n / 2) v[i] = i + 1;
		rep(i, n / 2, n) v[i] = n + n / 2 - i;
	} else {
		int n1 = n - 6, n2 = 6;
		{
			int m = (n1 - 2) / 2;
			rep(i, 0, n1) {
				for (int j = 1; j < m; j += 2) {
					ans.push_back({i, (i + j) % n1});
				}
			}
			rep(i, 0, n1 / 2) v[i] = i + 1;
			rep(i, n1 / 2, n1) v[i] = n + n1 / 2 - i;
		}
		{
			int m = (n2 - 2) / 2;
			rep(i, 0, n2) {
				for (int j = 1; j < m; j += 2) {
					ans.push_back({n1 + i, n1 + (i + j) % n2});
				}
			}
			rep(i, 0, n2 / 2) v[n1 + i] = i + 1 + n1 / 2;
			rep(i, n2 / 2, n2) v[n1 + i] = n - n1 / 2 + n2 / 2 - i;
		}
		rep(i, 0, n1) {
			int t = i & 1;
			rep(j, 0, 3) {
				ans.push_back({i, n1 + j * 2 + t});
			}
		}
	}
	for (auto& [x, y] : ans)
		if (x > y) swap(x, y);
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	cout << ans.size() << '\n';
	for (auto [i, j] : ans) cout << v[i] << ' ' << v[j] << '\n';
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}

Submission Info

Judge Result