和网上找的程序对拍了N久找不到bug。。。但是网上程序能ac我这个不行。。。思路都是一样的最大流构圖也一样的。。。
求数据啊。。
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;

const int MAXD = 40;
const int MAXDQ = 900;

int n;
int win[MAXD], defeat[MAXD];
int rem[MAXD][MAXD];
int pl[MAXD];
//int npl[30];
int zdWin[MAXD];
int sy[MAXD][MAXD];
int rm[MAXDQ];

int getIdx(int i, int j){
	if(i < j) return i*(n-1)+j;
	return j*(n-1)+i;
}

int mn(int a, int b){
	return (a<b) ? a : b;
}

void init(){
	for(int i = 0; i < n-1; i++){
		for(int j = 0; j < n-1; j++){
			sy[i][j] = 0;
		}
	}
	int nq = (n-1)*(n-1);
	for(int i = 0; i < nq; i++){
		rm[i] = 0;
	}
}

int pushFlow(){
	//cout << 1 << endl;
	int sprev[MAXD], tprev[MAXDQ];
	bool sused[MAXD] = {0}, tused[MAXDQ] = {0};
	int TOU = 5000;
	int zh = -1000;
	queue<int> bfs;
	for(int i = 0; i < n-1; i++){
		if(zdWin[i] > 0){
			sprev[i] = TOU;
			sused[i] = 1;
			bfs.push(i);
		}
	}
	while(!bfs.empty()){
		//cout << 1 << endl;
		int top = bfs.front();
		bfs.pop();
		if(top >= 0){
			for(int i = 0; i < n-1; i++){
				if(i == top) continue;
				int idx = getIdx(top, i);
				if(tused[idx]) continue;
				tused[idx] = 1;
				tprev[idx] = top;
				if(rm[idx] > 0){
					zh = idx;
					goto done;
				}
				bfs.push(-idx);
			}
		}
		else{
			int Top = -top;
			int i1 = Top/(n-1), i2 = Top%(n-1);
			if(!sused[i1] && (sy[i1][i2]>0)){
				sused[i1] = 1;
				sprev[i1] = top;
				bfs.push(i1);
			}
			if(!sused[i2] && (sy[i2][i1]>0)){
				sused[i2] = 1;
				sprev[i2] = top;
				bfs.push(i2);
			}
		}
	}
	//cout << 1 << endl;
	done:
	//cout << 1 << endl;
	if(zh == -1000) return 0;
	int flowVal = rm[zh];
	int cur = -zh, prev;
	while(1){
		//cout << 1 << endl;
		if(cur < 0){
			prev = tprev[-cur];
		}
		else{
			prev = sprev[cur];
			if(prev == TOU){
				flowVal = mn(flowVal, zdWin[cur]);
				break;
			}
			else{
				int Prev = -prev;
				int i1 = Prev/(n-1), i2 = Prev%(n-1);
				if(cur == i1) flowVal = mn(flowVal, sy[i1][i2]);
				else flowVal = mn(flowVal, sy[i2][i1]);
			}
		}
		cur = prev;
	}
	cur = -zh;
	rm[zh] -= flowVal;
	while(1){
		//cout << 1 << endl;
		if(cur < 0){
			prev = tprev[-cur];
		}
		else{
			prev = sprev[cur];
			if(prev == TOU){
				zdWin[cur] -= flowVal;
				break;
			}
			else{
				int Prev = -prev;
				int i1 = Prev/(n-1), i2 = Prev%(n-1);
				if(cur == i1) sy[i1][i2] -= flowVal;
				else sy[i2][i1] -= flowVal;
			}
		}
		cur = prev;
	}
	return flowVal;
}

int main() {
	int t;
	scanf("%d", &t);
	for(int ii = 0; ii < t; ii++){
		scanf("%d", &n);
		int sum = 0;
		for(int i = 0; i < n; i++){
			scanf("%d%d", &win[i], &defeat[i]);
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				scanf("%d", &rem[i][j]);
				if(i < j) sum += rem[i][j];
			}
		}
		if(n == 1){
			printf("1\n");
			continue;
		}
		//sum为剩余的总场数
		bool zhaodaole = 0;
		for(int i = 0; i < n; i++){
			init();
			int mxWin = win[i];
			int zong = sum;
			for(int j = 0; j < n; j++) {
				mxWin += rem[i][j];
				zong -= rem[i][j];
			}
			//最后流的值必须等于zong，否则不行
			//重新编號
			int bh = 0;
			for(int j = 0; j < n; j++){
				if(j == i) continue;
				pl[bh] = j;
				//npl[j] = bh;
				bh++;
			}
			//计算最多还能赢多少场
			bool ky = 1;
			for(int j = 0; j < n-1; j++){
				zdWin[j] = mxWin - win[pl[j]];
				if(zdWin[j] < 0){
					ky = 0;
					break;
				}
			}
			if(!ky) continue;
			for(int k = 0; k < n-2; k++){
				for(int j = k+1; j < n-1; j++){
					rm[getIdx(k, j)] = rem[pl[k]][pl[j]];
				}
			}
			int flow = 0;
			int tmpFlow;
			while(1){
				tmpFlow = pushFlow();
				//cout << tmpFlow << endl;
				if(tmpFlow <= 0) break;
				flow += tmpFlow;
			}
			//cout << flow << " " << zong << endl;
			if(flow == zong) {
				if(zhaodaole) printf(" ");
				printf("%d", i+1);
				zhaodaole = 1;
			}
		}
		printf("\n");
	}
	return 0;
}