#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
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;
queue<int> q;
q.push(i);
while(!q.empty()){
int cur = q.front();
q.pop();
if(cur == i and used[cur])
break;
if(used[cur] == 1)
return 0;
used[cur] = 1;
for(int j = 0; j < n; j ++){
if(p[cur][j] == 2){
d.merge(cur, j);
q.push(j);
ans[cur][j] = 1;
ans[j][cur] = 1;
break;
}
}
}
}
for(int i = 0; i < n; i ++){
if(used[i]){
queue<int> q;
q.push(i);
while(!q.empty()){
int cur = q.front();
q.pop();
for(int j = 0; j < n; j ++){
if(p[cur][j] == 1){
d.merge(cur, j);
q.push(j);
ans[cur][j] = 1;
ans[j][cur] = 1;
break;
}
}
}
}
}
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;
}
