#include<bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define sz(v) (int)(v.size())
#define f first
#define s second
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int sz = 1e3+5;
vector<pii>g[sz];
int usize[sz], par[sz], vis[sz], dist[sz];
void dijkstra(int node)
{
for(int i = 0; i < sz; i++)
{
vis[i] = 0;
dist[i] = 100000;
}
dist[node] = 0;
priority_queue<pii>pq;
pq.push({0, node});
while(!pq.empty())
{
int nd = pq.top().s;
pq.pop();
if(vis[nd])
continue;
vis[nd] = 1;
for(auto [u, w] : g[nd])
{
if(dist[u] > dist[nd] + w)
{
dist[u] = dist[nd] + w;
pq.push({-dist[u], u});
}
}
}
}
void makeset(int v)
{
par[v] = v;
usize[v] = 1;
}
int findpar(int v)
{
if(par[v] == v)
return v;
return par[v] = findpar(par[v]);
}
void unionsets(int a, int b)
{
a = findpar(a);
b = findpar(b);
if(a != b)
{
if(usize[a] > usize[b])
swap(a, b);
par[b] = a;
usize[a] += usize[b];
}
}
int construct(vector<vector<int>>p)
{
int n = sz(p);
int ctt = 0;
for(int i = 0; i < n; i++)
{
int ct = 0;
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
ct += (p[i][j] == 0 || p[i][j] == 2);
}
if(ct == n - 1)
ctt++;
}
if(ctt == n)
{
for(int i = 0; i < n; i++)
makeset(i);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(p[i][j] == 2)
unionsets(i, j);
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(p[i][j])
continue;
int u = i, v = j;
u = findpar(u);
v = findpar(v);
if(u == v)
{
return 0;
}
}
}
int grid[n][n];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
grid[i][j] = 0;
}
vi v[n];
for(int i = 0; i < n; i++)
{
int u = i;
u = findpar(u);
v[u].pb(i);
}
for(int i = 0; i < n; i++)
{
if(sz(v[i]) > 2)
{
for(int j = 0; j < sz(v[i]); j++)
{
int nxt = (j + 1) % sz(v[i]);
grid[v[i][nxt]][v[i][j]] = 1;
grid[v[i][j]][v[i][nxt]] = 1;
}
}
if(sz(v[i]) == 2)
{
return 0;
}
}
vector<vector<int>>answer;
for(int i = 0; i < n; i++)
{
vector<int>row;
for(int j = 0; j < n; j++)
row.pb(grid[i][j]);
answer.pb(row);
}
build(answer);
return 1;
}
for(int i = 0; i < n; i++)
makeset(i);
vi v;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
if(p[i][j] == 1)
unionsets(i, j);
if(p[i][j] == 3)
return 0;
}
}
set<int>vvv;
vi v2;
for(int i = 0; i < n; i++)
{
int cnt = 0;
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
if(p[i][j] == 0 || p[i][j] == 2)
cnt++;
}
if(cnt == n - 1){
v2.pb(i);
vvv.insert(i);
}
else
v.pb(i);
}
int grid[n][n];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
grid[i][j] = 0;
}
vi nw;
map<int, int>mp;
for(int i = 0; i < sz(v); i++)
{
int f = v[i];
f = findpar(f);
grid[v[i]][f] = 1;
grid[f][v[i]] = 1;
if(mp.find(f) == mp.end()){
nw.pb(f);
mp[f] = 1;
}
}
for(int i = 0; i < n; i++)
{
int f = i;
f = findpar(f);
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
int u = j;
u = findpar(u);
if(f == u && p[i][j] != 1)
return 0;
}
}
v = nw;
set<int>stt2;
set<int>st;
for(int i = 0; i < sz(v); i++)
{
int f = v[i];
vi v3;
if(st.find(f) == st.end())
{
st.insert(f);
v3.pb(f);
for(auto u : v2)
{
if(p[f][u]){
v3.pb(u);
stt2.insert(u);
}
}
for(auto u : v)
{
if(p[f][u] == 2){
v3.pb(u);
st.insert(u);
}
}
if(sz(v3) == 2)
return 0;
for(int j = 0; j < sz(v3); j++)
{
int nxt = (j + 1) % sz(v3);
grid[v3[j]][v3[nxt]] = 1;
grid[v3[nxt]][v3[j]] = 1;
}
}
}
nw.clear();
for(auto u : v2)
{
if(stt2.find(u) == stt2.end())
nw.pb(u);
}
for(int i = 0; i < n; i++)
makeset(i);
for(auto u : nw)
{
for(auto h : nw)
{
if(p[u][h] == 2)
{
unionsets(u, h);
}
}
}
stt2.clear();
vi y[n+5];
for(auto u : nw)
{
int f = u;
f = findpar(f);
y[f].pb(u);
}
for(int i = 0; i < n; i++)
{
if(sz(y[i]) == 2)
return 0;
if(sz(y[i]) >= 3){
v2.pb(i);
for(int j = 1; j < sz(y[i]); j++)
{
grid[y[i][j]][y[i][j-1]] = 1;
grid[y[i][j-1]][y[i][j]] = 1;
}
if(sz(y[i]) >= 3){
grid[y[i][0]][y[i].back()] = 1;
grid[y[i].back()][y[i][0]] = 1;
}
}
}
vector<vector<int>>ans;
for(int i = 0; i < n; i++)
{
vi res;
for(int j = 0; j < n; j++){
if(i == j)
grid[i][j] = 0;
res.pb(grid[i][j]);
}
ans.pb(res);
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j || !grid[i][j])
continue;
if(p[i][j] == 2)
{
g[i].pb({j, 1});
g[j].pb({i, 1});
}
else{
g[i].pb({j, 0});
g[j].pb({i, 0});
}
}
}
for(int i = 0; i < n; i++)
{
dijkstra(i);
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
if(p[i][j] == 0 && dist[j] != 100000)
return 0;
if(p[i][j] == 2 && (dist[j] == 0 || dist[j] == 100000))
return 0;
if(p[i][j] == 1 && dist[j] == 100000)
return 0;
}
}
build(ans);
return 1;
}
