#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1010;
struct DSU{
int dsu[mxn],sz[mxn];
DSU(){
iota(dsu,dsu+mxn,0);
fill(sz,sz+mxn,1);
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
a = root(a),b = root(b);
if(a == b)return;
if(sz[a]<sz[b])swap(a,b);
dsu[b] = a;
sz[a] += sz[b];
}
};
/*
std::vector<std::vector<int>> answer(n,vector<int>(n,0));
build(answer);
return 1;
*/
DSU chain,cyc;
int N;
vector<vector<int>> ans;
vector<vector<int>> tar;
vector<int> v[mxn];
int head[mxn];
void add_edge(int a,int b){
assert(a != b);
ans[a][b] = ans[b][a] = 1;
}
bool check(){
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
if(tar[i][j] == 0){
if(chain.root(i) == chain.root(j))return false;
}
else if(tar[i][j] == 1){
if(chain.root(i) != chain.root(j))return false;
}
else{
if(chain.root(i) == chain.root(j))return false;
int a = head[chain.root(i)],b = head[chain.root(j)];
if(cyc.root(a) != cyc.root(b))return false;
}
}
}
return true;
}
bitset<mxn> done;
bool CYCLE(){
for(int i = 0;i<N;i++){
if(done[i]||head[i] == -1)continue;
int now = head[i];
vector<int> v;
v.push_back(now);
bool has = false;
for(int j = 0;j<N;j++){
if(done[j])return false;
if(tar[now][j] == 2){
has = true;
v.push_back(head[chain.root(j)]);
}
}
if(!has)continue;
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
if(v.size()<=2)return false;
for(int i = 1;i<v.size();i++){
add_edge(v[i-1],v[i]);
cyc.onion(v[i-1],v[i]);
}
add_edge(v[0],v.back());
for(auto &i:v)done[chain.root(i)] = true;
}
return true;
}
int construct(std::vector<std::vector<int>> vvv) {
memset(head,-1,sizeof(head));
tar = vvv;
N = tar.size();
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
if(tar[i][j] == 1)chain.onion(i,j);
}
}
ans = vector<vector<int>>(N,vector<int>(N,0));
for(int i = 0;i<N;i++){
v[chain.root(i)].push_back(i);
}
for(int i = 0;i<N;i++){
for(int j = 1;j<v[i].size();j++){
add_edge(v[i][j-1],v[i][j]);
}
if(!v[i].empty())head[i] = v[i][0];
}
if(!CYCLE())return 0;
if(!check())return 0;
build(ans);
return 1;
}
