#include "supertrees.h"
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
//if it is in a cycle, all its values are 2
//we will never have >1 cycle in a component, otherwise >=4 ways to move
//bunch of paths leading into a cycle?
const int MAXN=1002;
int p[MAXN];
vector<int> c[MAXN];
int f(int x){
if (p[x]==x) return x;
return p[x]=f(p[x]);
}
void un(int a, int b){
if (p[a]==p[b]) return;
a=f(a); b=f(b);
if (SZ(c[a])<SZ(c[b])) swap(a,b);
FOR(i,SZ(c[b])) c[a].push_back(c[b][i]);
p[b]=a;
}
void init(int n){
FOR(i,n){
p[i]=i;
c[i].push_back(i);
}
}
int construct(vector<vector<int> > g){
int n=SZ(g);
init(n);
FOR(i,n){;
FOR(j,n) if (g[i][j]==1) un(i,j);
}
vector<vector<int> > ans;
ans.reserve(n);
FOR(i,n){
vector<int> tmp(n,0);
ans.push_back(tmp);
}
vector<int> pars;
FOR(i,n) if (p[i]==i) pars.push_back(i);
int m=SZ(pars);
FOR(i,m){
bool vis=false;
FOR(j,n) if (ans[pars[i]][j]) {vis=true; break;}
if (vis) continue;
vector<int> tmp;
tmp.push_back(pars[i]);
FOR(j,m){
if (g[pars[i]][pars[j]]==2){
tmp.push_back(pars[j]);
}
}
tmp.push_back(pars[i]);
FOR(j,SZ(tmp)-1){
if (tmp[j]==tmp[j+1]) continue;
ans[tmp[j]][tmp[j+1]]=ans[tmp[j+1]][tmp[j]]=1;
}
}
FOR(i,m){
int u=pars[i];
for (int v:c[u]){
if (v!=u) ans[u][v]=ans[v][u]=1;
}
}
bool can=true;
FOR(i,n){
FR(j,i+1,n){
int pi=f(i), pj=f(j);
if (g[i][j]==0){
if (pi==pj || g[pi][pj]!=0) can=false;
}
if (g[i][j]==1){
if (pi!=pj) can=false;
}
if (g[i][j]==2){
if (g[pi][pj]!=2) can=false;
}
if (!can) break;
}
if (!can) break;
}
if (!can) return 0;
build(ans);
return 1;
}
