#include <bits/stdc++.h> #include "supertrees.h" #define ll long long #define pll array<ll, 2> #define pb push_back using namespace std; ll n; vector<vector<int>>g; struct DSU{ vector<ll>e; DSU(ll n){e.assign(n + 1, -1);} ll find(ll x){ if(e[x] < 0) return x; return e[x] = find(e[x]); } bool unite(ll a, ll b){ a = find(a), b = find(b); if(a == b) return 0; if(e[a] > e[b]) swap(a, b); e[a] += e[b]; e[b] = a; return 1; } }; int construct(vector<vector<int>> p) { ll n = p.size(); DSU dsu(n); g.assign(n, vector<int>(n, 0)); for(ll i = 0; i < n; i++){ for(ll j = 0; j < n; j++){ if(p[i][j]) dsu.unite(i, j); if(p[i][j] == 3) return 0; } } for(ll i = 0; i < n; i++){ for(ll j = 0; j < n; j++){ ll rt1 = dsu.find(i); ll rt2 = dsu.find(j); if(!p[i][j] and rt1 == rt2) return 0; } } map<ll, vector<ll>>comp; for(ll i = 0; i < n; i++){ ll rt = dsu.find(i); comp[rt].pb(i); } for(auto &[rt , vv] : comp){ DSU ds(n); for(ll &i : vv){ for(ll &j : vv){ if(i == j) continue; if(p[i][j] == 1) ds.unite(i, j); } } for(ll &u : vv){ ll v = ds.find(u); if(u == v) continue; g[u][v] = g[v][u] = 1; } for(ll &i : vv){ for(ll &j : vv){ ll rt1 = ds.find(i); ll rt2 = ds.find(j); if(rt1 == rt2 and p[i][j] != 1) return 0; } } set<ll>st; for(ll &i : vv) st.insert(ds.find(i)); if(st.size() == 1) continue; if(st.size() == 2) return 0; for(ll i : st){ for(ll j : st){ if(i == j) continue; if(p[i][j] != 2) return 0; } } vector<ll>v; for(ll i : st) v.pb(i); for(ll i = 0; i < v.size(); i++){ g[v[i]][v[(i + 1) % v.size()]] = g[v[(i + 1) % v.size()]][v[i]] = 1; } } build(g); return 1; }