31 pts:WA

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=107;
int n, cnt=0;
bool e[N][N], e2[N][N];
bool vis[N], col[N];
int sz[N][2];
vector<int> id[N][2];
bool dp[N][N];int pre[N][N];
bool pd[N];int pos[N];
void dfs(int x, bool co){
	sz[cnt][co]++;
	id[cnt][co].push_back(x);
	vis[x]=1;col[x]=co;
	for(int i=1;i<=n;i++){
		if(e2[x][i]){
			if(!vis[i])
				dfs(i, (co^1));
			else if(col[i]==col[x]){
				cout<<"No solution"<<endl;
				exit(0);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int j;
		while((cin>>j) && j!=0)
			e[i][j]=1;
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(!(e[i][j] && e[j][i]) && (e[i][j] || e[j][i]))
				e2[i][j]=e2[j][i]=1;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cnt++;
			dfs(i, 1);
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<=n/2;j++){
			if(j>=sz[i][0] && dp[i-1][j-sz[i][0]])
				dp[i][j]=1, pre[i][j]=0;
			if(j>=sz[i][1] && dp[i-1][j-sz[i][1]])
				dp[i][j]=1, pre[i][j]=1;
		}
	}
	int ans=0;
	for(int i=n/2;i>=0;i--){
		if(dp[cnt][i]){
			ans=i;
			break;
		}
	}
	for(int i=cnt;i>=1;i--){
		for(int j=0;j<id[i][pre[i][ans]].size();j++)
			pd[pos[++pos[0]]=id[i][pre[i][ans]][j]]=1;
		ans-=sz[i][pre[i][ans]];
	}
	sort(pos+1, pos+pos[0]+1);
	cout<<pos[0]<<" ";
	for(int i=1;i<=pos[0];i++)
		cout<<pos[i]<<" ";
	cout<<endl;
	cout<<n-pos[0]<<" ";
	for(int i=1;i<=n;i++)
		if(!pd[i])
			cout<<i<<" ";
	cout<<endl;
	return 0;
}