求条

#include <bits/stdc++.h>
using namespace std;
int g[1010][1010], f[1010][1010], n;
int color[1010], cnt;
vector<int>vct[1010][4];
int from[1010][1010], xuan[1010][1010];
bool flag=false;
void dfs(int u, int col, int fa) {
	color[u] = col;
	f[cnt][col]++;
	vct[cnt][col].push_back(u);
	for (int i = 1; i <= n; ++i) {
		if(flag)return ;
		if (!g[i][u] && u != i && i != fa) {
			if (color[u] == color[i]) {
				flag=true;
				puts("No solution");
				return ;
			} else if (!color[i]) {
				dfs(i, 3 - col, u);
			}
		}
	}
}
int ans;
int v[1010];
int f2[1010][1010];
int T;
int main() {

 cin>>T;
	while(T--){
		flag=false;
			scanf("%d", &n);
			ans=0;
			memset(g, 0, sizeof(g));
			memset(color, 0, sizeof(color));
			cnt = 0;
			memset(f, 0, sizeof(f));
			memset(f2, 0, sizeof(f2));
			memset(xuan, 0, sizeof(xuan));
			memset(from, 0, sizeof(from));
			memset(v, 0, sizeof(v));
		for (int i = 1; i <= n; ++i) {
			int x = -1;
			while (x != 0) {
				scanf("%d", &x);
				g[i][x] = 1;
	
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = i + 1; j <= n; ++j)
				if (!(g[i][j] && g[j][i]))
					g[i][j] = g[j][i] = 0;
		}
	//	memset(color,-1,sizeof(color));
		for (int i = 1; i <= n; ++i) {
			if (!color[i]) {
				cnt++;
				dfs(i, 2, 0);
				if(flag)break;
			}
		}
		if(flag)continue;
		f2[0][0] = 1;
		for (int i = 1; i <= cnt; ++i) {
			for (int j = 0; j <= n / 2; ++j) {
				if (j >= f[i][1] && f2[i - 1][j - f[i][1]]) {
					f2[i][j] = 1;
					xuan[i][j] = 1;
					from[i][j] = j - f[i][1];
				}
				if (j >= f[i][2] && f2[i - 1][j - f[i][2]]) {
					f2[i][j] = 1;
					xuan[i][j] = 2;
					from[i][j] = j - f[i][2];
				}
	//			if (j >= f[i][1] && f[i - 1][j - f[i][1]]) {
	//				f[i][j] = 1;
	//				xuan[i][j] = 1;
	//				from[i][j] = j - f[i][1];
	//			}
	//			if (j >= f[i][2] && f[i - 1][j - f[i][2]]) {
	//				f[i][j] = 1;
	//				xuan[i][j] = 2;
	//				from[i][j] = j - f[i][2];
	//			}
			}
		}
		for (int i = n / 2; i >= 1; --i) {
			if (f2[cnt][i]) {
				ans = i;
				break;
			}
		}
		cout << ans << ' ';
		int i = cnt, j = ans;
		while (i > 0 && j > 0) {
			int col = xuan[i][j];
			for (int k = 0; k < vct[i][col].size(); k++) {
				v[vct[i][col][k]] = true;
			}
			j = from[i--][j];
		}
		for (i = 1; i <= n; ++i)
			if (v[i])
				printf("%d ", i);
		puts("");
		cout << n - ans << ' ';
		for (int i = 1; i <= n; ++i)
			if (!v[i])
				printf("%d ", i);
			puts("");
	}
	
	return 0;
}