#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> pp;
vector<vector<int>> adj;
int nn;
struct DSU
{
vector<int> e;
DSU(int _n)
{
e.assign(_n , -1);
}
int get(int u )
{
return (e[u] < 0 ? u : e[u] = get(e[u]));
}
bool same(int u , int v)
{
return get(u) == get(v);
}
void unite(int u , int v)
{
u = get(u) , v = get(v);
if(u == v)
return;
if(e[u] > e[v])
swap(u , v);
e[u]+=e[v];
e[v] = u;
}
};
bool check_conn()
{
DSU dsu(nn);
for(int i = 0 ; i < nn ;i++)
{
for(int j = 0 ; j < nn ; j++)
{
if(pp[i][j])
{
dsu.unite(i , j);
}
}
}
for(int i = 0 ; i < nn ; i++)
{
for(int j = 0 ; j < nn; j++)
{
if(pp[i][j] == 0 && dsu.same(i , j))
{
return 0;
}
}
}
DSU maker(nn);
for(int i = 0 ; i < nn ;i++)
{
for(int j = 0 ; j < nn ;j++)
{
if(pp[i][j] == 1)
{
maker.unite(i , j);
}
}
}
for(int i = 0 ; i < nn ; i++)
{
for(int j = 0 ; j < nn ; j++)
{
if(pp[i][j] >= 2 && maker.same(i , j))
{
return 0;
}
}
}
vector<vector<int>> comp(nn);
for(int i = 0 ; i < nn ; i++)
{
comp[dsu.get(i)].push_back(i);
}
for(auto c : comp)
{
vector<int> v;
map<int , vector<int>> trees;
for(auto i : c)
{
int par = maker.get(i);
trees[par].push_back(i);
if(i == par)
{
v.push_back(i);
continue;
}
adj[par][i] = 1;
adj[i][par] = 1;
}
if((int)v.size() == 1)
continue;
if((int)v.size() == 2)
{
return 0;
}
for(int i = 0 ; i < (int)v.size() ; i++)
{
adj[v[i]][v[(i + 1)%((int)v.size())]] = 1;
adj[v[(i + 1)%((int)v.size())]][v[i]] = 1;
}
}
build(adj);
return 1;
}
int construct(std::vector<std::vector<int>> P) {
pp = P;
nn = (int)pp.size();
adj.assign(nn , vector<int>(nn));
return check_conn();
}
