#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int first[110],nxt[2100],vv[2100],f[2100],ww[2100];int dep[110];int get(int i,int j){ int ans=-210000; while(i-j) {if(dep[i]>=dep[j]){ ans=max(ans,ww[i]); i=f[i];}else{ ans=max(ans,ww[j]); j=f[j];} } return ans;}int fa[210];inline int fin(int n){ if(n==fa[n])return n; return fa[n]=fin(fa[n]);}int w[2100];void dfs(int n){ int e; for(e=first[n];e;e=nxt[e])if(vv[e]-f[n]) {f[vv[e]]=n;dep[vv[e]]=dep[n]+1;dfs(vv[e]);ww[vv[e]]=w[e]; }}struct EE{ int u,v,w;}ee[11000];int cmp(EE a,EE b){ if(a.w==b.w)return a.u<b.u||(a.u==b.u&&a.v<b.v); return a.w<b.w;}struct ANS{ int a,b;}aa[110];int cmp1(ANS a,ANS b){ return a.a<b.a||(a.a==b.a&&a.b<b.b);}int kru(int m,int n){ int i,j,u,v,e=2; memset(first,0,sizeof(first)); for(i=1;i<=n;i++)fa[i]=i; sort(ee+1,ee+1+m,cmp); int t=0; for(i=1;i<=m;i++) {u=ee[i].u,v=ee[i].v;u=fin(u),v=fin(v);if(u==v) continue;fa[u]=v;t++;u=ee[i].u,v=ee[i].v;aa[t].a=u,aa[t].b=v; } if(t<n-1)return 0; return 1;}int ca[110][110];int main(){ int t,u,v,e,i,j,k,n,m; scanf("%d",&t); while(t--) {scanf("%d",&n);m=0;for(i=1;i<=n;i++){ for(j=1;j<=n;j++) {scanf("%d",&k);ca[i][j]=k;if(k==0) continue;++m;ee[m].u=i,ee[m].v=j;ee[m].w=k; }}if(!kru(m,n)) puts("-1");else{ sort(aa+1,aa+n,cmp1); for(i=1;i<n;i++)printf("%d %d%c",aa[i].a,aa[i].b,i==n-1?'n':' ');} }}
