// Source: https://usaco.guide/general/io #include <iostream> // cin, cout, cerr #include <vector> // vector #include <string> // string #include <set> #include "supertrees.h" #define vec vector #define mod 1000000007 #define For(i,n) for(int i = 0; i < n; i++) using namespace std; int komponenty(vec<vec<int>>& p, vec<vec<int>>& comp, vec<int>& t) { int n = p.size(); vec<int> kde(n, -1); for (auto i : t) { int zakl = 0; if (kde[i] == -1) { vec<int> s; s.push_back(i); comp.push_back(s); kde[i] = comp.size() - 1; zakl = 1; } int poc = 0; For(j, n) { if (p[i][j] == 0) continue; poc++; if (kde[j] == -1) { if (zakl) { kde[j] = kde[i]; comp[kde[i]].push_back(j); } else { return 0; } } if (kde[j] != kde[i]) { return 0; } } if (poc != comp[kde[i]].size()) return 0; } return 1; } int construct(vec<vec<int>> p) { int n = p.size(); vec<vec<int>> odp(n, vec<int>(n)); vec<vec<int>> comp; vec<int> t; For(i, n) { t.push_back(i); } cerr << "trolko" << endl; int da_sa = komponenty(p, comp, t); For(i, n) { For(j, n) { if (p[i][j] == 2) p[i][j] = 0; } } For(i, comp.size()) { if (comp[i].size() == 1) continue; vec<vec<int>> comp2; da_sa = komponenty(p, comp2, comp[i]); cerr << "comp[" << i << "] "; for (auto x : comp[i]) cerr << x << ' '; cerr << endl; For(j, comp2.size()) { For(k, comp2[j].size() - 1) { odp[comp2[j][k]][comp2[j][k+1]] = 1; odp[comp2[j][k+1]][comp2[j][k]] = 1; } int p1 = comp2[j][0]; int p2 = comp2[(j+1) % (comp2.size())][0]; odp[p1][p2] = 1; odp[p2][p1] = 1; } } build(odp); return 1; } /* int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); return 0; } */