#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;
int n, col[N];
bool vis[N];
int construct(vector<vector<int>> p) {
	n = p.size();
	vector<vector<int>> ans(n, vector<int>(n, 0)), f;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(p[i][j]) col[i]++;
			if(p[i][j] == 3) return 0;
		}
	}
	for(int i = 0; i < n; i++) {
		if(vis[i]) continue;
		vector<int> x;
		for(int j = 0; j < n; j++) {
			if(p[i][j]) {
				if(col[j] != col[i]) return 0;
				vis[j] = 1;
				x.push_back(j);
			}
		}
		for(int j : x) {
			for(int k : x) {
				if(!p[i][j]) {
					return 0;
				}
			}
		}
		f.push_back(x);
	}
	for(int i = 0; i < n; i++) {
		vis[i] = 0, col[i] = 0;
		for(int j = 0; j < n; j++) {
			if(p[i][j] == 1) {
				col[i]++;
			}
		}
	}
	for(auto v : f) {
		vector<int> rts;
		for(int j : v) {
			if(vis[j]) continue;
			vector<int> e;
			for(int k : v) {
				if(p[j][k] == 1) {
					e.push_back(k);
					vis[k] = 1;
					if(col[j] != col[k]) {
						return 0;
					}
				}
			}
			rts.push_back(j);
			for(int k = 0; k < (int)e.size() - 1; k++) {
				ans[e[k]][e[k + 1]] = ans[e[k + 1]][e[k]] = 1;
			}
		}
		if((int)rts.size() == 2) return 0;
		if((int)rts.size() > 2) {
			for(int i = 0; i < (int)rts.size(); i++) {
				int nx = (i + 1) % ((int)rts.size());
				ans[rts[i]][rts[nx]] = ans[rts[nx]][rts[i]] = 1;
			}
		}
	}
	build(ans);
	return 1;
}