중매쟁이

당신은 결혼 중개 회사 ACM(Amazing Coupling Marriage)의 담당자이며, 남성과 여성을 행복한 짝으로 이어 주는 것이 임무입니다.

$N$명의 남성과 $N$명의 여성이 되도록 빨리 결혼하고 싶어 합니다. 모든 남성은 $N$명의 여성 전부에 대한 선호 순위를 가지고 있고, 모든 여성도 $N$명의 남성 전부에 대한 선호 순위를 가지고 있습니다. 가장 선호하는 사람이 목록의 맨 앞에, 그다음으로 선호하는 사람이 그 뒤에 오는 식입니다. 아래 표는 남성 4명과 여성 4명이 가질 수 있는 선호 목록의 한 예입니다.

당신의 임무는 모든 남성을 여성과 일대일로 짝지어 그 결과가 안정적이 되게 하는 것입니다. 서로 결혼하지 않은 어떤 남성과 여성이 있는데, 그 둘이 각각 자신의 현재 배우자보다 상대방을 더 선호한다면, 그 짝짓기는 불안정합니다. 그런 남녀는 각자의 배우자를 버리고 서로를 택하려 하므로 결혼이 위태롭습니다. 그러한 쌍이 하나도 없으면 그 짝짓기는 안정적입니다.

예를 들어 남성 1이 여성 3과, 남성 2가 여성 1과, 남성 3이 여성 4와, 남성 4가 여성 2와 결혼하는 짝짓기는 불안정합니다. 남성 1은 여성 3보다 여성 1을 더 선호하고, 여성 1은 남성 2보다 남성 1을 더 선호하기 때문입니다.

주어진 선호 목록에 대해 보통 여러 개의 안정적인 짝짓기가 존재합니다. 그중에서 남성 최적 짝짓기를 출력하세요. 남성 최적 짝짓기란, 모든 남성이 어떤 안정적인 짝짓기에서든 얻을 수 있는 가장 좋은(자기 선호 목록에서 가장 위인) 상대를 얻게 되는 유일한 안정적 짝짓기입니다. 이는 자유로운 남성이 자기 목록을 따라 차례로 청혼하고 각 여성이 지금까지 청혼한 사람 중 가장 선호하는 사람을 붙잡는 남성 청혼 방식(게일-섀플리 알고리즘)이 만들어 내는 짝짓기와 정확히 같습니다.

첫째 줄에 테스트 케이스의 수 $T$가 주어집니다.

각 테스트 케이스의 첫 줄에는 정수 $N$이 주어지며 $1 \le N < 100$입니다. 남성과 여성이 각각 $N$명 있고, 모두 $1$번부터 $N$번까지 번호가 매겨져 있습니다.

이어지는 $N$개의 줄은 남성들의 선호를 나타냅니다. $i$번째 줄은 $1..N$의 순열로, 남성 $i$가 여성들에 대해 가진 선호 목록을 선호도가 높은 순서대로 담습니다(목록에서 여성 $X$가 여성 $Y$보다 앞에 있으면 남성 $i$는 $Y$보다 $X$를 더 선호합니다).

그다음 $N$개의 줄은 같은 형식으로 여성들의 선호를 나타냅니다. $j$번째 줄은 여성 $j$가 남성들에 대해 가진 선호 목록입니다.

각 테스트 케이스마다 남성 최적 안정 짝짓기를 나타내는 한 줄을 정확히 출력하세요.

그 줄에는 남성 번호가 커지는 순서대로 배우자인 여성의 번호를 나열합니다. 첫 번째 수는 남성 $1$의 배우자인 여성의 번호, 두 번째 수는 남성 $2$의 배우자인 여성의 번호이고, 일반적으로 $i$번째 수는 남성 $i$의 배우자인 여성의 번호입니다. 수들은 공백 하나로 구분합니다.