안정 결혼 문제

안정 결혼 문제는 서로 크기가 같은 두 집단의 구성원을, 상대 집단 구성원에 대한 선호에 따라 짝지어 주는 문제입니다. 입력으로 다음이 주어집니다.

• 남성 $n$명의 집합 $M$;
• 여성 $n$명의 집합 $F$;
• 각 남성마다 모든 $n$명의 여성을 가장 선호하는 순서부터 가장 덜 선호하는 순서까지 나열한 목록, 그리고 각 여성마다 모든 $n$명의 남성을 같은 방식으로 나열한 목록.

결혼이란 남성과 여성 사이의 일대일 대응입니다. 어떤 결혼이 안정적이라는 것은, 여성 $f$가 자신의 현재 상대보다 남성 $m$을 더 선호하고 동시에 $m$도 자신의 현재 상대보다 $f$를 더 선호하는 쌍 $(m, f)$가 존재하지 않는다는 뜻입니다. 안정적인 결혼이 남성 최적이라는 것은, 어떤 남성이 여기에서 배정받은 여성보다 더 선호하는 여성과 짝지어지는 다른 안정적인 결혼이 존재하지 않는다는 뜻입니다.

남성과 여성의 선호 목록이 주어질 때, 남성 최적 안정 결혼을 구하세요.

첫째 줄에 테스트 케이스의 수가 주어집니다. 각 테스트 케이스는 다음과 같이 주어집니다.

• 정수 $n$ ($0 < n < 27$)이 적힌 한 줄;
• $n$명의 남성 이름과 이어서 $n$명의 여성 이름을 공백으로 구분해 나열한 한 줄. 각 남성 이름은 소문자 한 글자, 각 여성 이름은 대문자 한 글자입니다;
• x:P 형식의 $n$개 줄. 여기서 x는 남성 이름이고 P는 그가 선호하는 순서(가장 선호하는 여성부터)대로 나열한 모든 $n$명의 여성 이름 문자열입니다;
• X:p 형식의 $n$개 줄. 여기서 X는 여성 이름이고 p는 그녀가 선호하는 순서대로 나열한 모든 $n$명의 남성 이름 문자열입니다.

각 테스트 케이스마다 남성 최적 안정 결혼의 쌍들을 한 줄에 하나씩 m F 형식(남성 이름, 공백 하나, 그의 상대 이름)으로, 남성 이름의 오름차순으로 정렬해 출력합니다. 연속된 테스트 케이스 사이에는 빈 줄을 하나 출력합니다.