#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
struct DisjointSetUnion{
int N;
vector<int>sz;
vector<int>link;
DisjointSetUnion(int n): N(n){
sz.resize(n);
link.resize(n);
for (int i = 0; i < n; i++){
link[i] = i;
sz[i] = 1;
}
}
int Find(int a){
if (a == link[a])return a;
return link[a] = Find(link[a]);
}
bool Unite(int a, int b){
a = Find(a), b = Find(b);
if (a == b)return false;
if (sz[a] < sz[b])swap(a,b);
sz[a] += sz[b];
link[b] = a;
return true;
}
};
class Uniderected_Graph{
public:
int N, mx = 0, far = 0;
vector<vector<int>>adj;
vector<int>Visited;
Uniderected_Graph(int _N) : N(_N){
adj.resize(N);
Visited.resize(N);
Visited.assign(N,0);
}
void Add_Edge(int A, int B){
adj[A].push_back(B);
adj[B].push_back(A);
}
void Far(int u, int p, int depth = 0){
if (depth > mx){
mx = depth;
far = u;
}
Visited[u] = 1;
for (int& nxt : adj[u]){
if (nxt == p)continue;
Far(nxt, u, depth + 1);
}
}
pair<int,int> Find_Diameter(int Source){
mx = -1, far = 0;
Far(Source,Source,0);
int A = far;
mx = -1, far = 0;
Far(A,A,0);
int B = far;
return make_pair(A,B);
}
void Dfs(int u,vector<int>& p){
if (Visited[u])return;
Visited[u] = 1;
p.push_back(u);
for (int& nxt : adj[u]){
Dfs(nxt, p);
}
}
vector<int>pracka(int Source){
vector<int>ans;
Dfs(Source,ans);
return ans;
}
};
int construct(vector<vector<int>> p) {
int n = (int)p.size();
vector<vector<int>>adj(n,vector<int>(n));
DisjointSetUnion DSU(n + 1);
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (p[i][j] == 3)return 0;
if (p[i][j] == 1){
DSU.Unite(i,j);
}
}
}
//check if all p[i][j] = 1 in trees, otherwise contradiction
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int A = DSU.Find(i) , B = DSU.Find(j);
if (p[i][j] != 1 && A == B){
return 0;
}
if (A != i){
adj[A][i] = adj[i][A] = 1;
}
if (B!=j){
adj[B][j] = adj[j][B] = 1;
}
}
}
//All good
//merge trees in cycle
Uniderected_Graph G(n+1);
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int A = DSU.Find(i), B = DSU.Find(j);
if (A == B)continue;
//Different component
if (p[A][B] == 2){
G.Add_Edge(A,B);
}
}
}
for (int i = 0; i < n; i++){
if (G.Visited[i])continue;
auto response = G.pracka(i);
if (response.size() == 1)continue;
if (response.size() == 2)return 0;
adj[response[0]][response.back()] = 1;
adj[response.back()][response[0]] = 1;
DSU.Unite(response.back(), response[0]);
for (int j = 1; j < (int)response.size(); j++){
adj[response[j]][response[j-1]] = 1;
adj[response[j-1]][response[j]] = 1;
DSU.Unite(response[j],response[j-1]);
}
}
//check if trees merged in cycle and have p[i][j] = 0, should be in another component
//check if all needed are in same component
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int A = DSU.Find(i) , B = DSU.Find(j);
if (p[i][j] == 0 && A == B)return 0;
if (p[i][j] != 0 && A != B)return 0;
}
}
build(adj);
return 1;
}
