#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define MAXN 1001
int N;
int parent[MAXN],siz[MAXN];
vector<vector<int>> adj;
vector<pair<int,int>> edges;
vector<int> korenovi,comp;
int get(int node)
{
if (parent[node]==node) return node;
return get(parent[node]);
}
void unite(int node1,int node2)
{
node1=get(node1),node2=get(node2);
if (node1==node2) return;
if (siz[node1]<siz[node2]) swap(node1,node2);
parent[node2]=node1;siz[node1]+=siz[node2];
adj[node1][node2]=adj[node2][node1]=1;
}
int construct(std::vector<std::vector<int>> p)
{
int N=p.size();adj.resize(N);
for (int node=0;node<N;node++) {parent[node]=node;siz[node]=1;adj[node].resize(N);}
for (int node1=0;node1<N;node1++)
{
for (int node2=node1+1;node2<N;node2++)
{
if (p[node1][node2]==3 or p[node1][node2]!=p[node2][node1]) return 0;
if (p[node1][node2]==1) edges.push_back({node1,node2});
}
}
for (pair<int,int> par:edges) unite(par.first,par.second);
for (int node=0;node<N;node++)
{
int kompnode=get(node);
for (int sled=node+1;sled<N;sled++)
{
if (p[node][sled]!=0) continue;
int kompsled=get(sled);if (kompnode==kompsled) return 0;
}
}
for (int node=0;node<N;node++)
{
if (parent[node]==node) comp.push_back(node);
}
for (int poz=0;poz<comp.size();poz++)
{
int node=comp[poz];if (parent[node]!=node) continue;
korenovi.push_back(node);
for (int sledpoz=poz+1;sledpoz<comp.size();sledpoz++)
{
int sled=comp[sledpoz];
if (parent[sled]!=sled and p[node][sled]==2) return 0;
if (parent[sled]==sled and p[node][sled]==2) korenovi.push_back(sled);
}
if (korenovi.size()==2) return 0;
if (korenovi.size()==1) {korenovi.clear();continue;}
for (int poz1=0;poz1<korenovi.size()-1;poz1++) {int node1=korenovi[poz1],node2=korenovi[poz1+1];adj[node1][node2]=adj[node2][node1]=1;parent[node2]=node;siz[node]+=siz[node2];}
int node1=korenovi[0],node2=korenovi[korenovi.size()-1];adj[node1][node2]=adj[node2][node1]=1;korenovi.clear();
}
for (int node=0;node<N;node++)
{
int kompnode=get(node);
for (int sled=node+1;sled<N;sled++)
{
if (p[node][sled]!=0) continue;
int kompsled=get(sled);if (kompnode==kompsled) return 0;
}
}
for (int node=0;node<N;node++) adj[node][node]=0;
build(adj);return 1;
};
