#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;
int dsu[mxN];
int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
void merge(int a, int b) { dsu[find(b)] = find(a); }
int construct(std::vector<std::vector<int>> p)
{
vector<vector<int>> b;
int n = p.size(), m = p.size();
b.resize(n);
for (int i = 0; i < n; i++)
dsu[i] = i;
for (int i = 0; i < n; i++)
b[i].resize(m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == j)
continue;
if (p[i][j] == 1)
{
if (find(i) != find(j))
{
merge(i, j);
b[i][j] = 1;
b[j][i] = 1;
}
}
}
}
vector<vector<int>> ty;
vector<set<int>> v;
v.resize(n);
ty.resize(n);
for (int i = 0; i < n; i++)
{
ty[i].resize(n);
for (int j = 0; j < m; j++)
{
ty[i][j] = -1;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == j)
continue;
if (find(i) == find(j))
{
if (p[i][j] != 1)
return 0;
}
else
{
if (ty[i][find(j)] != -1 && p[i][j] != ty[i][find(j)])
return 0;
if (p[i][j] == 2)
v[find(i)].insert(find(j));
ty[i][find(j)] = p[i][j];
}
}
}
vector<bool> vis(n);
for (int i = 0; i < n; i++)
{
int prv = -1;
v[i].insert(i);
for(auto x : v[i]){
for(int j = 0;j < n;j++){
if(x == j) continue;
if(v[i].find(j) != v[i].end() && p[x][j] != 2) return 0;
}
}
if (vis[i])
continue;
if (v[i].size() == 2)
return 0;
for (auto x : v[i])
{
vis[x] = 1;
if (prv != -1)
{
b[x][prv] = 1;
b[prv][x] = 1;
}
prv = x;
}
if (v[i].size() >= 2)
{
b[*v[i].begin()][*v[i].rbegin()] = 1;
b[*v[i].rbegin()][*v[i].begin()] = 1;
}
}
build(b);
return 1;
}
