using namespace std;
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#define ll long long
set<ll> v[50*50+1];
map<pair<ll, ll>, ll> m;
void haku(ll y, ll x, map<pair<ll,ll>,ll> g)
{
set<ll> s = v[g[{y, x}]];
pair<ll, ll> u = { y - 1,x }, r = { y,x + 1 }, d = { y + 1,x }, l = { y,x - 1 };
vector<pair<ll,ll>> c;
ll n = 0;
if (y > 1)
{
if (!g[u])
{
n++; c.push_back(u);
}
else if (s.count(g[u]))s.erase(g[u]);
}
if (x < 3)
{
if (!g[r])
{
n++; c.push_back(r);
}
else if (s.count(g[r]))s.erase(g[r]);
}
if (y < 3)
{
if (!g[d])
{
n++; c.push_back(d);
}
else if (s.count(g[d]))s.erase(g[d]);
}
if (x > 1)
{
if (!g[l])
{
n++; c.push_back(l);
}
else if (s.count(g[l]))s.erase(g[l]);
}
if (n == 0 && s.empty())
{
m = g; return;
}
if (n < s.size())
return;
else
{
vector<ll> s1(s.begin(), s.end());
vector<vector<pair<ll,ll>>> c1;
if (n > s1.size())
{
}
else c1.push_back(c);
for (auto i : c1)
{
do
{
map<pair<ll, ll>, ll> g1 = g;
pair<ll, ll> p;
bool b = true;
for (ll j=0;j<s1.size();j++)
{
for (auto k : g1)
{
if (k.second == s1[j])b = false;
cout << "Dub "<< k.second << endl;
}
if (!b)break;
g1[i[j]] = s1[j];
p = i[j];
b = true;
}
if(b)
haku(p.first, p.second, g1);
} while (next_permutation(s1.begin(), s1.end()));
}
}
}
int main()
{
ifstream f("Syote.txt");
for (ll i = 1; i <= 100; i++)
{
vector<ll> u;
for (ll j = 1; j <= 100; j++)
{
ll x;
f >> x;
u.push_back(x);
cout << x << " ";
}
cout << endl;
for (ll j = 0; j < 100; j++)
{
if (j > 0)
v[u[j]].insert(u[j - 1]);
if (j < 99)
v[u[j]].insert(u[j + 1]);
}
}
vector<ll> a;
for (ll i = 1; i <= 50*50; i++)
{
if (v[i].size() < 3)a.push_back(i);
}
ll n = 0;
while (m.empty() && n < a.size())
{
map<pair<ll, ll>, ll> g;
g[{1, 1}] = a[n];
haku(1, 1, g);
n++;
}
if (m.empty())cout << "QAQ";
else
{
for (ll i = 1; i <= 50; i++)
{
for (ll j = 1; j <= 50; j++)
{
cout << m[{i, j}] << " ";
}
cout << endl;
}
}
}