#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){ if(vv.size() == 1) continue; set<ll>cycle; pll cnt = {0, 0}; for(ll i = 1; i < vv.size(); i++){ cnt[p[vv[0]][vv[i]] - 1]++; } if(cnt[0] and !cnt[1]){ for(ll i = 1; i < vv.size(); i++){ g[vv[0]][vv[i]] = g[vv[i]][vv[0]] = 1; } continue; } map<ll, set<ll>>ones; vector<bool>ch(n, 0); for(ll &i : vv){ if(ch[i]) continue; ll c = 0; for(ll &j : vv){ if(i == j) continue ; c += (p[i][j] > 1); } if(c == vv.size() - 1) cycle.insert(i); else{ for(ll &j : vv){ if(i == j) continue; if(p[i][j] == 1){ ones[i].insert(j); ch[j] = 1; } } } ch[i] = 1; } if(ones.size() + cycle.size() < 3) return 0; vector<ll>path; for(auto &[x, adj] : ones){ for(ll i : adj){ g[i][x] = 1; g[x][i] = 1; } path.pb(x); } ll prev = *cycle.begin(); for(ll i : cycle){ if(i == prev) continue; g[i][prev] = 1; g[prev][i] = 1; prev = i; } for(ll i = 0; i < path.size(); i++){ g[prev][path[i]] = 1; g[path[i]][prev] = 1; prev = path[i]; } g[*cycle.begin()][prev] = 1; g[prev][*cycle.begin()] = 1; } build(g); return 1; }