#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define print(a) for(auto x : a) cout << x << ' '; cout << endl;
struct DSU {
int size = 1;
vector<int> par, sz;
DSU (int n){
par.resize(n);
sz.resize(n);
for(int i = 0; i < n; i ++)
par[i] = i, sz[i] = 1;
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a == b)
return;
if(sz[a] < sz[b])
swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
int find(int n){
if(par[n] != n)
return par[n] = find(par[n]);
return par[n];
}
};
int construct(vector<vector<int>> p) {
int n = (int)p.size();
DSU d(n);
vector<vector<int>> ans(n, vector<int> (n));
vector<bool> used(n + 1);
for(int i = 0; i < n; i ++){
if(used[i])
continue;
vector<int> nodes;
int cur = i, sz = 1;
nodes.push_back(i);
while(sz){
sz --;
used[cur] = 1;
for(int j = 0; j < n; j ++){
if(p[cur][j] == 2 and !used[j]){
bool flag = 1;
for(auto y : nodes){
if(p[j][y] != 2){
flag = 0;
break;
}
}
if(flag){
nodes.push_back(j);
d.merge(cur, j);
ans[cur][j] = 1;
ans[j][cur] = 1;
cur = j;
sz ++;
break;
}
}
}
}
if(nodes.size() == 1)
continue;
if(p[nodes.front()][nodes.back()] != 2)
return 0;
d.merge(nodes.front(), nodes.back());
ans[nodes.front()][nodes.back()] = 1;
ans[nodes.back()][nodes.front()] = 1;
}
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(p[i][j] == 0 and d.find(i) == d.find(j))
return 0;
if(p[i][j] == 1 and d.find(i) != d.find(j)){
d.merge(i, j);
ans[i][j] = 1;
ans[j][i] = 1;
}
}
}
build(ans);
return 1;
}
