#include "supertrees.h"
#include <vector>
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
class DSU{
private:
vi par, sz;
public:
DSU(int n){
par.resize(n);
iota(all(par), 0);
sz.resize(n, 1);
}
int find(int a){
if(par[a]==a) return a;
return par[a] = find(par[a]);
}
void merge(int a, int b){
a = find(a), b = find(b);
if(a==b) return;
if(sz[a]<sz[b]) swap(a, b);
sz[a] += sz[b];
par[b] = a;
}
bool same(int a, int b){
a = find(a), b = find(b);
return a==b;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
DSU dsu(n);
vector<vi> adj(n, vi(n, 0));
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(p[i][j]==1){
if(!dsu.same(i, j)){
adj[i][j] = adj[j][i] = 1;
dsu.merge(i, j);
}
}
}
}
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(p[i][j]==3) return 0;
if(p[i][j]!=1){
if(dsu.same(i, j)) return 0;
}
}
}
vb visited(n, 0);
for(int i = 0; i < n; i++){
if(dsu.find(i)!=i || visited[i]) continue;
set<int> neighboor; neighboor.insert(i);
for(int j = i+1; j < n; j++){
if(p[i][j]==2){ neighboor.insert(dsu.find(j)); dsu.merge(i, j); }
}
vi nodes(all(neighboor));
if(nodes.size()==2) return 0;
if(nodes.size()==1) continue;
for(int k = 0; k < (int)nodes.size()-1; k++) adj[nodes[k]][nodes[k+1]] = adj[nodes[k+1]][nodes[k]] = 1;
adj[nodes[0]][nodes.back()] = adj[nodes.back()][nodes[0]] = 1;
for(auto x: nodes) visited[x] = 1;
}
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(p[i][j]==0){
if(dsu.same(i, j)) return 0;
}
}
}
build(adj);
return 1;
}
