#include using namespace std; using ll = long long; using Clock = chrono::steady_clock; constexpr int MAX_W = 300000; constexpr double TIME_LIMIT = 1.9; struct Edge { int u, v, w; }; vector make_edges(int n) { vector e; for (int r = 0; r + 1 < n; ++r) for (int c = 0; c < n; ++c) e.push_back({r * n + c, (r + 1) * n + c, 1}); for (int r = 0; r < n; ++r) for (int c = 0; c + 1 < n; ++c) e.push_back({r * n + c, r * n + c + 1, 1}); return e; } // 1: valid, 0: duplicate, -1: time up int check(int v, const vector& e, Clock::time_point deadline) { vector>> g(v); for (auto [a, b, w] : e) { g[a].push_back({b, w}); g[b].push_back({a, w}); } unordered_set seen; seen.reserve((size_t)v * (v - 1) / 2); const ll INF = (1LL << 60); vector dist(v); for (int s = 0; s < v; ++s) { if (Clock::now() >= deadline) return -1; fill(dist.begin(), dist.end(), INF); priority_queue, vector>, greater>> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { auto [d, x] = pq.top(); pq.pop(); if (d != dist[x]) continue; for (auto [y, w] : g[x]) if (dist[y] > d + w) { dist[y] = d + w; pq.push({dist[y], y}); } } for (int t = s + 1; t < v; ++t) if (!seen.insert(dist[t]).second) return 0; } return 1; } void output(int n, const vector& e) { int k = 0; for (int r = 0; r + 1 < n; ++r) { for (int c = 0; c < n; ++c) cout << (c ? " " : "") << e[k++].w; cout << '\n'; } for (int r = 0; r < n; ++r) { for (int c = 0; c + 1 < n; ++c) cout << (c ? " " : "") << e[k++].w; cout << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int v = n * n; auto e = make_edges(n); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution weight(1, MAX_W); auto deadline = Clock::now() + chrono::duration_cast(chrono::duration(TIME_LIMIT)); while (Clock::now() < deadline) { for (auto& x : e) x.w = weight(rng); int result = check(v, e, deadline); if (result == 1) { output(n, e); return 0; } if (result < 0) break; } cout << -1 << '\n'; }