#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long int lld;
#define trav(a,v) for(auto a:v)
class DSU{
int sz[1000000];
int parent[1000000];
int n;
public:
void init(int N){
n=N;
rep(i,0,n)sz[i]=1,parent[i]=i;
}
int root(int x){
if(x==parent[x])return x;
parent[x]=root(parent[x]);
return parent[x];
}
void merge(int a, int b){
a=root(a);
b=root(b);
if(a==b)return;
if(sz[a]<sz[b])swap(a,b);
sz[a]+=sz[b];
parent[b]=a;
}
};
DSU D;
DSU D2;
vector<int> comp[1000000];
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
D.init(n);
rep(i,0,n){
rep(j,0,n){
if(p[i][j]==1)D.merge(i,j);
}
}
rep(i,0,n)comp[D.root(i)].push_back(i);
rep(i,0,n){
bool B=true;
rep(j,i+1,n){
if(D.root(j)==D.root(i)){
B=false;
if(p[i][j]!=1){
return 0;
}
}
}
if(B){
rep(j,0,i){
if(D.root(j)==D.root(i))answer[i][j]=1,answer[j][i]=1;
}
}
}
rep(i,0,n){
rep(j,0,n){
if(p[i][j]==2){
D2.merge(D.root(i),D.root(j));
}
}
}
vector<pair<int,int> >V;
rep(i,0,n){
if(D.root(i)==i){
V.push_back({D2.root(i),i});
}
}
sort(V.begin(),V.end());
int bg=V[0].second;
rep(i,0,V.size()){
if(i<V.size()-1 && V[i].first==V[i+1].first){
answer[V[i].second][V[i+1].second]=1;
answer[V[i+1].second][V[i].second]=1;
}else{
if(answer[V[i].second][bg]==1){
return 0;
}else{
answer[V[i].second][bg]=1;
answer[bg][V[i].second]=1;
}
if(i<V.size())bg=V[i+1].second;
}
}
rep(i,0,n){
rep(j,0,n){
if(p[i][j]==0 && D2.root(D.root(i))==D2.root(D.root(j))){
return 0;
}
}
}
build(answer);
return 1;
}
