#include "supertrees.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
using namespace std;
/*
Disjoint Set Union: Union by rank, size of each component is maintained.
Usage: dsu(n) -> creates dsu for elements 0 to n-1, with each element as its own component
find_set(v) -> as usual
union_sets(a,b) -> as usual
size_containing(v) -> gives size of component containing vertex v
*/
class dsu {
public:
vector<int> parent;
vector<int> size;
vector<int> rnk;
dsu(int n) {
parent.assign(n, 0);
for (int i = 0; i < n; i++)
parent[i] = i;
size.assign(n, 1);
rnk.assign(n, 0);
}
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (rnk[a] < rnk[b])
swap(a, b);
parent[b] = a;
if (rnk[a] == rnk[b])
rnk[a]++;
size[a] += size[b];
}
}
int size_containing(int a) { return size[find_set(a)]; }
};
int construct(std::vector<std::vector<int>> p) {
int n = sz(p);
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
dsu d(n);
rep(i,0,n-1)
rep(j,0,n-1)
if(p[i][j]!=0)
d.union_sets(i,j);
rep(i,0,n-1)
rep(j,0,n-1)
if(p[i][j]==0 && d.find_set(i)==d.find_set(j))
return 0;
rep(i,0,n-1)
rep(j,0,n-1)
if(p[i][j]==3)
return 0;
vector <int> comps[n];
rep(i,0,n-1)
comps[d.find_set(i)].push_back(i);
rep(compno,0,n-1)
if(sz(comps[compno])>1)
{
dsu ds(n);
int s=sz(comps[compno]);
rep(i,0,s-1)
rep(j,0,s-1)
{
int v1=comps[compno][i];
int v2=comps[compno][j];
if(p[v1][v2]==1)
ds.union_sets(v1,v2);
}
rep(i,0,s-1)
rep(j,0,s-1)
{
int v1=comps[compno][i];
int v2=comps[compno][j];
if(p[v1][v2]==2 && ds.find_set(v1)==ds.find_set(v2))
return 0;
}
vector <int> seqs[n];
for(auto v:comps[compno])
seqs[ds.find_set(v)].push_back(v);
vector <int> cntc;
rep(i,0,n-1)
if(sz(seqs[i])>0)
cntc.push_back(i);
if(sz(cntc)==2)
return 0;
rep(i,0,n-1)
if(sz(seqs[i])>0)
for(auto x:seqs[i])
if(x!=i)
answer[x][i]=answer[i][x]=1;
s=sz(cntc);
rep(i,0,s-2)
{
int v1=cntc[i];
int v2=cntc[i+1];
answer[v1][v2]=answer[v2][v1]=1;
}
int v1=cntc[0];
int v2=cntc[s-1];
answer[v1][v2]=answer[v2][v1]=1;
}
build(answer);
return 1;
}
// signed main()
// {
// vector <vector<int>> p={{1,1,2,2},{1,1,2,2},{2,2,1,2},{2,2,2,1}};
// construct(p);
// return 0;
// }
