#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> cycle;
cycle.push_back(i);
bool flag = 1;
for(int j = 0; j < n; j ++){
if(p[i][j] == 2){
if(used[j])
flag = 0;
else
cycle.push_back(j);
}
}
for(int j = 1; j < (int)cycle.size(); j ++){
int x = cycle[j], cnt = 0;
for(int j = 0; j < n; j ++)
if(p[x][j] == 2)
cnt ++;
if(cnt != (int)cycle.size()){
flag = 0;
break;
}
for(auto y : cycle){
if(x != y and p[x][y] != 2){
flag = 0;
break;
}
}
if(!flag)
break;
}
if(flag and (int)cycle.size() > 1){
for(int i = 1; i <= (int)cycle.size(); i ++){
ans[cycle[i - 1]][cycle[i % (int)cycle.size()]] = 1;
ans[cycle[i % (int)cycle.size()]][cycle[i - 1]] = 1;
d.merge(cycle[i - 1], cycle[i % (int)cycle.size()]);
used[cycle[i % (int)cycle.size()]] = 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;
}
