#ifndef rtgsp
#include "worldmap.h"
#endif // rtgsp
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1602;
int n, m, cnt, diag, d[maxn], from[maxn], to[maxn], mx[maxn], best[maxn];
bool visited[maxn];
vector<int> euler, be[maxn], adj[maxn];
void dfs (int u)
{
euler.push_back(u);
visited[u] = true;
for (int v : adj[u])
{
if (visited[v])
{
if (d[u] < d[v])
{
from[++cnt] = u;
to[cnt] = v;
}
}
else
{
d[v] = d[u] + 1;
dfs(v);
euler.push_back(u);
}
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B)
{
n = N; m = M; cnt = 0; euler.clear();
vector<vector<int>> mp(2*n, vector<int>(2*n, 1));
for (int i = 1; i <= n; i++)
{
d[i] = 0;
mx[i] = 0;
visited[i] = false;
be[i].clear();
adj[i].clear();
}
for (int i = 0; i < m; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1);
for (int i = 0; i < 2*n - 1; i++)
mx[euler[i]] = max(mx[euler[i]], min(i, 2*n - 2 - i));
for (int i = 1; i <= cnt; i++)
{
if (mx[from[i]] < mx[to[i]]) swap(from[i], to[i]);
be[from[i]].push_back(to[i]);
}
for (int i = 0; i < 2*n - 1; i++)
{
if (mx[euler[i]] == min(i, 2*n - 2 - i))
best[euler[i]] = i;
}
diag = 0;
for (int i = 0; i < 2*n - 1; i++)
{
if (best[euler[i]] != i)
{
for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
mp[j][diag - j] = euler[i];
diag++;
}
else
{
for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
mp[j][diag - j] = euler[i];
diag++;
int cur = 0;
for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
{
if (cur < (int)be[euler[i]].size()) mp[j][diag - j] = be[euler[i]][cur];
else mp[j][diag - j] = euler[i];
cur++;
}
diag++;
for (int j = max(0, diag - (2*n - 1)); j <= min(diag, 2*n - 1); j++)
mp[j][diag - j] = euler[i];
diag++;
visited[euler[i]] = true;
}
}
return mp;
}
#ifdef rtgsp
int main()
{
freopen(task".in", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s;
int T;
cin >> s >> T >> T;
while (T--)
{
int N, M;
vector<int> A, B;
A.clear(); B.clear();
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int x, y;
cin >> x >> y;
A.push_back(x);
B.push_back(y);
}
auto mp = create_map(N, M, A, B);
for (auto i : mp)
{
for (auto j : i)
cout << j << " ";
cout << '\n';
}
}
}
#endif // rtgsp
