#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
struct DisjointSetUnion{
int N;
vector<int>sz;
vector<int>link;
DisjointSetUnion(int n): N(n){
sz.resize(n);
link.resize(n);
for (int i = 0; i < n; i++){
link[i] = i;
sz[i] = 1;
}
}
int Find(int a){
if (a == link[a])return a;
return link[a] = Find(link[a]);
}
bool Unite(int a, int b){
a = Find(a), b = Find(b);
if (a == b)return false;
if (sz[a] < sz[b])swap(a,b);
sz[a] += sz[b];
link[b] = a;
return true;
}
};
int construct(vector<vector<int>> p) {
int n = (int)p.size();
vector<vector<int>>adj(n,vector<int>(n));
DisjointSetUnion DSU(n + 1);
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){
DSU.Unite(i,j);
}
}
}
//check if all p[i][j] = 1 in trees, otherwise contradiction
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int A = DSU.Find(i) , B = DSU.Find(j);
if (p[i][j] != 1 && A == B){
return 0;
}
if (A != i){
adj[A][i] = adj[i][A] = 1;
}
if (B!=j){
adj[B][j] = adj[j][B] = 1;
}
}
}
//All good
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int A = DSU.Find(i), B = DSU.Find(j);
if (A == B)continue;
//Different component
if (p[A][B] == 2){
adj[A][B] = adj[B][A] = 1;
}
}
}
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (adj[i][j]){
DSU.Unite(i,j);
}
}
}
//check if trees merged in cycle and have p[i][j] = 0, should be in another component
//check if all needed are in same component
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int A = DSU.Find(i) , B = DSU.Find(j);
if (p[i][j] == 0 && A == B)return 0;
if (p[i][j] != 0 && A != B)return 0;
}
}
build(adj);
return 1;
}
