#include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>#include<math.h>#include<iostream>#include<vector>#include<queue>#define re return#define ct continue#define pr printf#define sc scanf#define ffr(x) for(int i = head[x] ; i!= -1 ; i =ed[i].nt)#define me(a,i) memset(a,i,sizeof(a))#define fr(i,t,n) for(int i = t ; i <= n ; i++)#define ft(i,t,n) for(int i = n ; i >= t ; i--)using namespace std;const int N = 810;const int INF = 1000000000;int vx[N],vy[N],F[N][N],slack[N],my[N],mx[N],ux[N],uy[N],n1,n2;bool find(int x){ ux[x] = 1; fr(i,1,n2) { int tmp = vx[x] + vy[i] - F[x][i]; if(!uy[i] && tmp <= 0) { uy[i] = 1; if(!my[i] || find(my[i])) { mx[x] = i; my[i] = x; re 1; } } else if(!uy[i] && tmp > 0) slack[i] = min(slack[i] , tmp); } re 0;}void work(){ me(mx,0); me(my,0); me(vx,0); me(vy,0); fr(i,1,n1) { vx[i] = -INF; fr(j,1,n2) vx[i] = max(vx[i] , F[i][j]); } fr(i,1,n1) { while(1) { fr(j,1,n2) { ux[j] = uy[j] = 0; slack[j] = INF; } if(find(i)) break; int d = INF; fr(j,1,n2) if(!uy[j]) d=min(d,slack[j]); fr(j,1,n2) { if(ux[j])vx[j] -= d; if(uy[j])vy[j] += d; } } } fr(i,1,n1) { if(F[i][mx[i]] > 0)pr("%d",mx[i]); else pr("0"); if(i < n1)pr(" "); else pr("n"); }}void addadge(int x , int y ,int t){ F[x][y] = t;}int w[N];int main(){ int test , n , m , as; sc("%d",&test); while(test--) { sc("%d",&n); fr(i,1,n) sc("%d",&w[i]); fr(i,1,n) fr(j,1,n) F[i][j] = -INF; fr(i,1,n) { sc("%d",&m); while(m--) { sc("%d",&as); addadge(i,as,w[i]*w[i]); } } n1 = n2 = n; work(); if(test)puts(""); }}
