#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=1e3+5;
int n,color[mxn],k,color2[mxn],sz,lst,arr[mxn][mxn];
vector<int>vt[mxn];
vector<int>vt2[mxn];
vector<vector<int>>p;
void dfs(int u){
color[u]=k;
sz++;
for(int v:vt[u]){
if(!color[v]){
arr[u][v]=1;
arr[v][u]=1;
dfs(v);
}
}
}
void dfs2(int u){
color2[u]=k;
sz++;
lst=u;
for(int v:vt[u]){
if(!color[v]&&!color2[v]){
arr[u][v]=1;
arr[v][u]=1;
dfs2(v);
}
}
}
int construct(vector<vector<int>> pp) {
p=pp;
n=p.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]==1){
vt[i+1].pb(j+1);
vt[j+1].pb(i+1);
}
else if(p[i][j]==2){
vt[i+1].pb(j+1);
vt[j+1].pb(i+1);
}
else if(p[i][j]==3){
return 0;
}
}
}
for(int i=1;i<=n;i++){
if(!color[i]){
k=i;
sz=0;
dfs(i);
if(sz==1){
color[i]=0;
}
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(color[i]>0&&color[i]==color[j]&&p[i-1][j-1]!=1){
return 0;
}
}
}
vector<pii>v;
for(int i=1;i<=n;i++){
if(color[i]) continue;
k=i;
sz=0;
dfs2(i);
if(lst==i){
color2[i]=0;
}
else{
arr[i][lst]=1;
arr[lst][i]=1;
v.pb({i,lst});
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(color2[i]>0&&color2[i]==color2[j]&&p[i-1][j-1]!=2){
return 0;
}
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(p[i-1][j-1]==2&&!(color2[i]&&color2[j])){
if(color2[i]){
int a=color2[i],b=color[j];
arr[a][b]=1;
arr[b][a]=1;
}
else{
int a=color[i],b=color2[j];
arr[a][b]=1;
arr[b][a]=1;
}
}
}
}
vector<vector<int>>ans;
for(int i=1;i<=n;i++){
vector<int>vt;
for(int j=1;j<=n;j++){
vt.pb(arr[i][j]);
}
ans.pb(vt);
}
build(ans);
return 1;
}
