Ghép Cặp Ổn Định

Có hai nhóm, mỗi nhóm gồm $n$ người. Ta gọi các thành viên của nhóm thứ nhất là $A_1,A_2,\dots ,A_n$, còn các thành viên của nhóm thứ hai là $B_1,B_2,\dots ,B_n$. Mỗi người xếp hạng toàn bộ thành viên của nhóm còn lại theo thứ tự yêu thích, từ cao xuống thấp. Không có hai người cùng hạng trong một danh sách.

Hãy ghép mỗi người của nhóm $A$ với đúng một người của nhóm $B$ sao cho phép ghép ổn định.

Một cặp $(A_i,B_j)$ được gọi là cặp gây bất ổn nếu $A_i$ và $B_j$ không đang được ghép với nhau, đồng thời:

• $A_i$ thích $B_j$ hơn người đang ghép với mình;
• $B_j$ thích $A_i$ hơn người đang ghép với mình.

Một phép ghép là ổn định khi không tồn tại cặp gây bất ổn.

Input

• Dòng đầu chứa số bộ test $t$.
• Mỗi bộ test có dạng:
• Dòng đầu chứa số nguyên $n$.
• $n$ dòng tiếp theo mô tả thứ tự yêu thích của nhóm $B$. Mỗi dòng bắt đầu bằng chỉ số $b$, sau đó là một hoán vị của $1,\dots ,n$, cho biết $B_b$ xếp các thành viên nhóm $A$ theo thứ tự từ thích nhất đến ít thích nhất.

• $n$ dòng tiếp theo mô tả thứ tự yêu thích của nhóm $A$ theo cách tương tự. Mỗi dòng bắt đầu bằng chỉ số $a$, sau đó là một hoán vị của $1,\dots ,n$ gồm các chỉ số của nhóm $B$.

• Các dòng mô tả trong mỗi nhóm không nhất thiết xuất hiện theo thứ tự chỉ số.

Output

• Với mỗi bộ test, in đúng $n$ dòng. Mỗi dòng chứa hai số nguyên $a$ $b$, nghĩa là $A_a$ được ghép với $B_b$.

• Mỗi chỉ số của hai nhóm phải xuất hiện đúng một lần. Không in dòng trống hoặc ký hiệu phân cách giữa hai bộ test. Nếu có nhiều phép ghép ổn định, bạn có thể in bất kỳ phép ghép nào.

Constraints

• $1\le t\le 100$.
• $1\le n\le 500$ trong mỗi bộ test.
• Mỗi danh sách yêu thích là một hoán vị đầy đủ của $1,\dots ,n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $t\le 10$ và $n\le 9$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

1
3
1 2 1 3
2 1 2 3
3 1 2 3
1 1 2 3
2 1 2 3
3 2 3 1

1 2
2 1
3 3