#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)
vector<vector<int>> comp;
vector<int> par;
void Connect(int i,int j){
i=par[i]; j=par[j];
if(i==j) return;
if(sz(comp[i])<sz(comp[j])) swap(i,j);
for(int x:comp[j]){
comp[i].pb(x);
par[x]=i;
}
comp[j].clear();
}
int construct(vector<vector<int>> p) {
int N=sz(p);
comp.resize(N); par.resize(N);
for(int i=0;i<N;i++){
comp[i].pb(i); par[i]=i;
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(p[i][j]==3) return 0;
if(p[i][j]) Connect(i,j);
}
}
vector<vector<int>> answer(N,vector<int>(N));
vector<bool> vis(N,false);
for(vector<int> c:comp){
//Debug(c);
if(sz(c)==2 && p[c[0]][c[1]]) return 0;
for(int i:c){
for(int j:c){
if(p[i][j]==0) return 0;
}
}
vector<int> cycle,tmp;
for(int u:c){
if(!vis[u]){
for(int v:c){
if(p[u][v]==1){
tmp.pb(v);
vis[v]=true;
}
}
cycle.pb(u);
for(int i=1;i<sz(tmp);i++){
int u=tmp[i],v=tmp[i-1];
answer[u][v]=1;
answer[v][u]=1;
}
//Debug(tmp);
tmp.clear();
}
}
//Debug(cycle);
if(!cycle.empty()){
for(int i=0;i<sz(cycle);i++){
if(i==0){
int u=cycle[0],v=cycle.back();
answer[u][v]=1;
answer[v][u]=1;
}
else{
int u=cycle[i],v=cycle[i-1];
answer[u][v]=1;
answer[v][u]=1;
}
}
}
}
build(answer);
return 1;
}
