There are given n men and n women.
Each woman ranks all men in order of her preference
(her first choice, her second choice, and so on).
Similarly, each man sorts all women according to
his preference. The goal is to arrange n
marriages in such a way that if a man m
prefers some woman w more than his wife, and w prefers m more then her husband a new marriage occurs between w and m.  If w prefers her husband more, then she stays married to him.  This problem always has a solution and your task is to find one.


Input
The first line contains a positive integer t ≤ 100
indicating the number of test cases. Each test case is an
instance of the stable marriage problem defined above.
The first line of each test case is a positive integer
n ≤ 500 (the number of marriages to find).
The next n lines are the woman's preferences: ith
line contains the number i (which means that this is the list given
by the ith woman) and the numbers of men
(the first choice of ith woman, the second choice,...).
Then, the men's preferences follow in the same format.


Output
For each test case print n lines, where each line
contains two numbers m and w, which means that
the man number m and the woman number w should get married.


Example

Input:
2
4
1 4 3 1 2
2 2 1 3 4
3 1 3 4 2
4 4 3 1 2
1 3 2 4 1
2 2 3 1 4
3 3 1 2 4
4 3 2 4 1
7
1 3 4 2 1 6 7 5
2 6 4 2 3 5 1 7
3 6 3 5 7 2 4 1
4 1 6 3 2 4 7 5
5 1 6 5 3 4 7 2
6 1 7 3 4 5 6 2
7 5 6 2 4 3 7 1
1 4 5 3 7 2 6 1
2 5 6 4 7 3 2 1
3 1 6 5 4 3 7 2
4 3 5 6 7 2 4 1
5 1 7 6 4 3 5 2
6 6 3 7 5 2 4 1
7 1 7 4 2 6 5 3



Output:
1 3
2 2
3 1
4 4
1 4
2 5
3 1
4 3
5 7
6 6
7 2


Warning: large Input/Output data, be careful with certain languages
from sets import Set 
a = int(raw_input())
for k in range(a):
    women_list= []
    men_list = []
    
    women_propsed = []
    men_rejected = Set()  # set of unique rejected 
    
    
    noofpair = int(raw_input())
    for one in range(noofpair):
        women_list.append([])
        men_list.append([])
        women_propsed.append([])
        
    for one in range(noofpair):
        men_order=str(raw_input())
        order_m =men_order.split(" ")
        indice = order_m.pop(0)
        interlist = map(int,order_m)
        intlist = [x-1 for x in interlist]
        women_list[int(indice)-1] =intlist 
    for one in range(noofpair):
        women_order=str(raw_input())
        order_wm = women_order.split(" ")
        indicew = order_wm.pop(0)
        interlist = map(int,order_wm)
        intlist = [x-1 for x in interlist]
        men_list[int(indicew)-1] =intlist 
    
    #print women_list
    #print men_list

    #
    # ALL MEN PROPOSES 
    #
    for ss in range(len(men_list)):
            temp = men_list[ss].pop(0)
            women_propsed[temp].append(ss)
            #print ss
            #print women_propsed
    
    while True : 
        #
        # WOMEN REJECT LOWER ONE'S
        #
        for dd in range(len(women_propsed)):
            if (len(women_propsed[dd])>1):
                templis= women_propsed[dd][:]
                rank = []
                
                for ii in templis :
                    rank.append(women_list[dd].index(ii))
                
                minrank = min(rank)
                indexrank = rank.index(minrank)
                
                prefer_man =templis.pop(indexrank)
                
                women_propsed[dd] = [prefer_man]
                
                for aass in templis :
                    men_rejected.add(aass)
                #print men_rejected
        #
        # MEN REJECTED PROPOSES AGAIN
        #
        if len(men_rejected)==0:
            break 
        else :
            while(len(men_rejected)>0):
                men = men_rejected.pop()
                temp = men_list[men].pop(0)
                women_propsed[temp].append(men)
    woman_pair = []
    for ss in range(len(women_propsed)):
        woman_pair.append(women_propsed[ss][0])
    for tty in range(len(woman_pair)):
        print str(tty+1)+" "+str(woman_pair.index(tty)+1)