#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
// Men and women are represented by integers 1...N
// ManPref is the preference list of all men for all women.
// ManPref[m][i] = w iff w is at ith position in the preference list of m
// WomanPref is the preference list of all women for all men.
// WomanPref[w][i] = m iff m is at ith position in the preference list of w
// Ranking gives the ranking of each man in the preference list of each woman
// Ranking[w][m] = i iff WomanPref[w][i] = m
// Current gives the current engagement of each women
// Current[w] = m iff w is currently engaged to m
// Next gives the index of next woman to propose to in the preference list of each man
// Next[m] = i iff m has proposed to all w s.t. ManPref[m][j] = w for j = 1...i-1 but not ManPref[m][i]
int Ranking[505][505], ManPref[505][505], WomanPref[505][505], Next[505], Current[505];
int main() {
int T, N, i, j, m, w;
// list of men who are not currently engaged
queue <int> freeMen;
scanf("%d", &T); // No. of test cases
while (T--) {
scanf("%d", &N); // No. of men and women
for (i = 1; i <= N; i++) {
scanf("%d", &w); // Woman number (b/w 1 and N) followed by her preference list
for (j = 1; j <= N; j++)
scanf("%d", &WomanPref[w][j]);
}
for (i = 1; i <= N; i++) {
scanf("%d", &m); // Man number (b/w 1 and N) followed by his preference list
for (j = 1; j <= N; j++)
scanf("%d", &ManPref[m][j]);
}
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
Ranking[i][WomanPref[i][j]] = j;
memset(Current, 0, (N + 1) * sizeof(int));
for (i = 1; i <= N; i++) {
freeMen.push(i);
Next[i] = 1;
}
while (!freeMen.empty()) {
m = freeMen.front();
w = ManPref[m][Next[m]++];
if (Current[w] == 0) {
Current[w] = m;
freeMen.pop();
} else if (Ranking[w][m] < Ranking[w][Current[w]]) {
freeMen.pop();
freeMen.push(Current[w]);
Current[w] = m;
}
}
// (m, w) pairs in the stable matching
for (w = 1; w <= N; w++)
printf("%d %d\n", Current[w], w);
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxxdWV1ZT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIE1lbiBhbmQgd29tZW4gYXJlIHJlcHJlc2VudGVkIGJ5IGludGVnZXJzIDEuLi5OCgovLyBNYW5QcmVmIGlzIHRoZSBwcmVmZXJlbmNlIGxpc3Qgb2YgYWxsIG1lbiBmb3IgYWxsIHdvbWVuLgovLyBNYW5QcmVmW21dW2ldID0gdyBpZmYgdyBpcyBhdCBpdGggcG9zaXRpb24gaW4gdGhlIHByZWZlcmVuY2UgbGlzdCBvZiBtCgovLyBXb21hblByZWYgaXMgdGhlIHByZWZlcmVuY2UgbGlzdCBvZiBhbGwgd29tZW4gZm9yIGFsbCBtZW4uCi8vIFdvbWFuUHJlZlt3XVtpXSA9IG0gaWZmIG0gaXMgYXQgaXRoIHBvc2l0aW9uIGluIHRoZSBwcmVmZXJlbmNlIGxpc3Qgb2YgdwoKLy8gUmFua2luZyBnaXZlcyB0aGUgcmFua2luZyBvZiBlYWNoIG1hbiBpbiB0aGUgcHJlZmVyZW5jZSBsaXN0IG9mIGVhY2ggd29tYW4KLy8gUmFua2luZ1t3XVttXSA9IGkgaWZmIFdvbWFuUHJlZlt3XVtpXSA9IG0KCi8vIEN1cnJlbnQgZ2l2ZXMgdGhlIGN1cnJlbnQgZW5nYWdlbWVudCBvZiBlYWNoIHdvbWVuCi8vIEN1cnJlbnRbd10gPSBtIGlmZiB3IGlzIGN1cnJlbnRseSBlbmdhZ2VkIHRvIG0KCi8vIE5leHQgZ2l2ZXMgdGhlIGluZGV4IG9mIG5leHQgd29tYW4gdG8gcHJvcG9zZSB0byBpbiB0aGUgcHJlZmVyZW5jZSBsaXN0IG9mIGVhY2ggbWFuCi8vIE5leHRbbV0gPSBpIGlmZiBtIGhhcyBwcm9wb3NlZCB0byBhbGwgdyBzLnQuIE1hblByZWZbbV1bal0gPSB3IGZvciBqID0gMS4uLmktMSBidXQgbm90IE1hblByZWZbbV1baV0KaW50IFJhbmtpbmdbNTA1XVs1MDVdLCBNYW5QcmVmWzUwNV1bNTA1XSwgV29tYW5QcmVmWzUwNV1bNTA1XSwgTmV4dFs1MDVdLCBDdXJyZW50WzUwNV07CgppbnQgbWFpbigpICB7CiAgICBpbnQgVCwgTiwgaSwgaiwgbSwgdzsKCiAgICAvLyBsaXN0IG9mIG1lbiB3aG8gYXJlIG5vdCBjdXJyZW50bHkgZW5nYWdlZAogICAgcXVldWUgPGludD4gZnJlZU1lbjsKCiAgICBzY2FuZigiJWQiLCAmVCk7ICAgIC8vIE5vLiBvZiB0ZXN0IGNhc2VzCiAgICB3aGlsZSAoVC0tKSB7CiAgICAgICAgc2NhbmYoIiVkIiwgJk4pOyAgICAvLyBOby4gb2YgbWVuIGFuZCB3b21lbgogICAgICAgIGZvciAoaSA9IDE7IGkgPD0gTjsgaSsrKSB7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZ3KTsgICAgLy8gV29tYW4gbnVtYmVyIChiL3cgMSBhbmQgTikgZm9sbG93ZWQgYnkgaGVyIHByZWZlcmVuY2UgbGlzdAogICAgICAgICAgICBmb3IgKGogPSAxOyBqIDw9IE47IGorKykKICAgICAgICAgICAgICAgIHNjYW5mKCIlZCIsICZXb21hblByZWZbd11bal0pOwogICAgICAgIH0KICAgICAgICBmb3IgKGkgPSAxOyBpIDw9IE47IGkrKykgewogICAgICAgICAgICBzY2FuZigiJWQiLCAmbSk7ICAgIC8vIE1hbiBudW1iZXIgKGIvdyAxIGFuZCBOKSBmb2xsb3dlZCBieSBoaXMgcHJlZmVyZW5jZSBsaXN0CiAgICAgICAgICAgIGZvciAoaiA9IDE7IGogPD0gTjsgaisrKQogICAgICAgICAgICAgICAgc2NhbmYoIiVkIiwgJk1hblByZWZbbV1bal0pOwogICAgICAgIH0KCiAgICAgICAgZm9yIChpID0gMTsgaSA8PSBOOyBpKyspCiAgICAgICAgICAgIGZvciAoaiA9IDE7IGogPD0gTjsgaisrKQogICAgICAgICAgICAgICAgUmFua2luZ1tpXVtXb21hblByZWZbaV1bal1dID0gajsKCiAgICAgICAgbWVtc2V0KEN1cnJlbnQsIDAsIChOICsgMSkgKiBzaXplb2YoaW50KSk7CgogICAgICAgIGZvciAoaSA9IDE7IGkgPD0gTjsgaSsrKSB7CiAgICAgICAgICAgIGZyZWVNZW4ucHVzaChpKTsKICAgICAgICAgICAgTmV4dFtpXSA9IDE7CiAgICAgICAgfQoKICAgICAgICB3aGlsZSAoIWZyZWVNZW4uZW1wdHkoKSkgICAgewogICAgICAgICAgICBtID0gZnJlZU1lbi5mcm9udCgpOwogICAgICAgICAgICB3ID0gTWFuUHJlZlttXVtOZXh0W21dKytdOwogICAgICAgICAgICBpZiAoQ3VycmVudFt3XSA9PSAwKSAgIHsKICAgICAgICAgICAgICAgIEN1cnJlbnRbd10gPSBtOwogICAgICAgICAgICAgICAgZnJlZU1lbi5wb3AoKTsKICAgICAgICAgICAgfSBlbHNlIGlmIChSYW5raW5nW3ddW21dIDwgUmFua2luZ1t3XVtDdXJyZW50W3ddXSkgIHsKICAgICAgICAgICAgICAgIGZyZWVNZW4ucG9wKCk7CiAgICAgICAgICAgICAgICBmcmVlTWVuLnB1c2goQ3VycmVudFt3XSk7CiAgICAgICAgICAgICAgICBDdXJyZW50W3ddID0gbTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLy8gKG0sIHcpIHBhaXJzIGluIHRoZSBzdGFibGUgbWF0Y2hpbmcKICAgICAgICBmb3IgKHcgPSAxOyB3IDw9IE47IHcrKykKICAgICAgICAgICAgcHJpbnRmKCIlZCAlZFxuIiwgQ3VycmVudFt3XSwgdyk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=